% ---------
% Compile with "pdflatex hw0".
% --------
%!TEX TS-program = pdflatex
\documentclass[11pt]{article}
\usepackage{jeffe,handout,graphicx,mathtools,url}
%!TEX encoding = UTF-8 Unicode
\usepackage[utf8x]{inputenc} % Allow some non-ASCII Unicode in source
\usepackage{enumerate}
\usepackage{stmaryrd}
\def\Sym#1{\textbf{\texttt{\color{BrickRed}#1}}}
% ---------
% The next following lines change the default text and math fonts and
% make a few other minor cosmetic changes. If you get any error
% messages related to these packages, just comment them out. -- Jeff
% --------
\usepackage[charter]{mathdesign}
\usepackage{berasans,beramono}
\SetMathAlphabet{\mathsf}{bold}{\encodingdefault}{\sfdefault}{b}{\updefault}
\SetMathAlphabet{\mathtt}{bold}{\encodingdefault}{\ttdefault}{b}{\updefault}
\SetMathAlphabet{\mathsf}{normal}{\encodingdefault}{\sfdefault}{\mddefault}{\updefault}
\SetMathAlphabet{\mathtt}{normal}{\encodingdefault}{\ttdefault}{\mddefault}{\updefault}
\usepackage{microtype}
% ---------
% End of cosmetics.
% --------
% ---------
% Redefine suits
% --------
\usepackage{pifont}
\def\Spade{\text{\ding{171}}}
\def\Heart{\text{\textcolor{Red}{\ding{170}}}}
\def\Diamond{\text{\textcolor{Red}{\ding{169}}}}
\def\Club{\text{\ding{168}}}
% ---------
% Dashed lines in arrays
% --------
\usepackage{arydshln}
\dashlinedash 0.75pt
\dashlinegap 1.5pt
\hidesolutions
% -----
% Additional notation
% -----
\usepackage{xspace}
\newcommand{\pos}{\ensuremath{\mathrm{pos}}\xspace}
% =========================================================
\begin{document}
\headers{“CS 374”}{Homework 1}{Fall 2015}
\thispagestyle{empty}
\begin{center}
\LARGE
\textbf{“CS 374” Fall 2015 --- Homework 9}
\\
\Large Due Wednesday, November 18, 2015 at 10am
\end{center}
\bigskip
\bigskip
\bigskip
\hrule
\begin{center}
\Large \textbf{••• Some important course policies •••}\\
\end{center}
\hrule
\bigskip
\begin{itemize}
\item \textbf{You may work in groups of up to three people.} However, each problem should be submitted by exactly one person, and the beginning of the homework should clearly state the names and NetIDs of each person contributing.
\item \textbf{You may use any source at your disposal}—paper,
electronic, or human—but you \EMPH{must} cite \EMPH{every} source
that you use. See the academic integrity policies on the course web
site for more details. For all future homeworks, groups of up to
three students will be allowed to submit joint solutions.
\item
\textbf{Submit your pdf solutions in Moodle.}
See instructions on the course website and submit a separate pdf
for each problem. Ideally, your solutions should be typeset in LaTex. If you hand write your homework make sure that the pdf scan is easy to read. Illegible scans will receive no points.
\item
\textbf{Avoid the Three Deadly Sins!} There are a few dangerous writing (and thinking) habits that will trigger an automatic zero on any homework or exam problem. Yes, we are completely serious.
\begin{itemize}\itemsep0pt
\item Give complete solutions, not just examples.
\item Declare all your variables.
\item Never use weak induction.
\end{itemize}
\item
Unlike previous editions of this and other theory courses we are not
using the “I don’t know” policy.
\end{itemize}
\bigskip
\hrule
\begin{center}
\large \textbf{See the course web site for more information.}\\[2ex]\normalsize
If you have any questions about these policies,\\
please don’t hesitate to ask in class, in office hours, or on Piazza.
\end{center}
\hrule
\vfil
\vfil
\vfil
\newpage
\begin{enumerate}
\parindent 1.5em \itemsep 3ex plus 0.5fil
%----------------------------------------------------------------------
\def\arraystretch{1.2}
%----------------------------------------------------------------------
\item Several years ago, a popular data storage medium for computers was {\em punched paper tape}
(see \url{http://en.wikipedia.org/wiki/Punched\_tape}). One of the problems with punched tape was that it could only be written once - since once the holes are punched to indicate a character, there was no way to erase the character. Thus, it was a reasonable permanent storage medium, but not very good for working memory. Nonetheless, as you will show in this problem, it is sufficient for any computation that a TM could otherwise do.
Consider an arbitrary one-tape Turing machine $M$ with input alphabet $\{0,1\}$ and tape alphabet $\{0,1,B\}$. Describe how a punched-tape variant $M'$ of $M$ can simulate $M$, where the conventions for $M'$ are as follows.
\begin{itemize}
\item $M'$ has a read-only input tape, with end markers \$, and with tape cells that are either unpunched (0), or punched (1). There cannot be more than one punch in any tape cell. The read head can move back and forth along the input tape, but cannot punch (write) on this tape.
\item $M'$ has a single work tape, initially all unpunched. It may move back and forth along the work tape, and punch a cell if it so chooses. Once punched, a cell may not become unpunched.
\item $M'$ can determine whether a cell has been punched or not.
\item $M'$ otherwise works as a normal TM would. That is, in a single move,
based on its current state, whether or not the cells currently scanned on
the input tape and work tape are punched, it may punch the work tape (or
not), independently move the heads on the input and work tape left, right,
or (for convenience) stay in the same cell, and change state.
\end{itemize}
Describe how $M'$ can be used to simulate $M$. You need not fully describe
the states and transitions of $M'$ in terms of those of $M$, but you should
give sufficient detail that the states and transitions could be created from
your description. Be sure to describe in detail how a single move of $M$
is simulated by $M'$. If $M$ on input $w$ takes $k$ steps before halting,
roughly how many steps does your $M'$ take? (Asymptotic bounds are fine,
e.g., $O(k), O(k \log k), O(k^2),$ etc. Also, you do {\em not} need to
optimize the efficiency of $M'$.)
\item
In the lecture, we saw one language $EQUAL$ such that neither
$EQUAL$ nor $\overline{EQUAL}$ is recursively enumerable. In this
exercise you will see one way to construct more examples of such languages.
\begin{enumerate}
\item For any two languages $L_1, L_2$, give a language $L'$ such that
both $L_1 \le L'$ and $L_2 \le L'$.
\item Show that if $L$ is a recursively enumerable language that is not
recursive, and both $L \le L'$ and $\overline{L} \le L'$, then neither
$L'$ nor $\overline{L'}$ is recursively enumerable.
\end{enumerate}
%----------------------------------------------------------------------
% \item A {\em number-coder} for a language $L$ is a TM which on input an
% integer $i\in\N$ outputs $f(i)$, where $f:\N\rightarrow L$ is a one-to-one
% function. Show that a language has a number-coder if and only if it is
% recognizable.
\item Define a {\em TM generator} as a TM with a single work tape and also
a special write-only output tape. Initially, the work tape is blank (i.e.,
no input) with its head at the left-most cell, and the output tape is blank
except for a $\#$ at the left most cell with its write head one cell to the
right of that. From time to time, depending on its computation on the work
tape, the generator may write a character in $\{0,1,\#\}$ on the output tape
and move the output head to the right. It is said to {\em generate} a
string $w\in\{0,1\}^*$ if at some point in time, $\#w\#$ appears as a
substring of the string on the output tape. The language generated by a TM
generator $G$, denoted by $L(G)$, is the set of all strings that $G$ ever
generates. Prove that a language $L$ is recursively enumerable if and only
if $L = L(G)$ for some TM generator $G$. Note that you need to show both
directions separately.
\end{enumerate}
\end{document}
%----------------------------------------------------------------------