\documentclass{article}
\input{6045preamble}
\newcommand{\spacechar}{\sqcup}
\newcommand{\length}[1]{\left \vert #1 \right \vert}

\begin{document}
\homework{4}{Prof. Ron Rivest}{Due: 13 March 2002}{Your name here}

\begin{problem}
  \textbf{[Turing Machines]} In this problem, we ask you to write out
  the specification of a Turing machine in the format used in Monday's
  lecture. (This is also the format used on pages 132 and 133.)
  Instead of recognizing a language, however, we want a Turing machine
  that will calculate a \emph{function} of its input. That is, on
  input $w$, your Turing machine should always halt and accept, but
  when it does the tape should contain exactly $f(w)$ for some
  function $f$.
  
  In this problem, the tape alphabet $\Gamma$ will consist of three
  things:
  \begin{itemize}
  \item $\Sigma$, the input alphabet, 
  \item $\dot{\Sigma}$, the characters of the input alphabet with dots
    over them, and
  \item Three special symbols: $\spacechar$ (space), $x$, and
    $\rightarrow$.
  \end{itemize}

  For this problem, the function $f$ is defined to be the sequence of
  characters:
  $$x^{\length{w}}\rightarrow W \rightarrow$$
  where $W$ is
  the word $w$ with a space character $\spacechar$ inserted after each
  character of $w$ and a dot over the first character of $w$. So,
  $f(01010)$ would be, for example:
  $$xxxxx\rightarrow \dot{0} \spacechar 1 \spacechar 0
  \spacechar 1 \spacechar 0 \spacechar \rightarrow$$
  
  One last condition: your Turing machine can only write once to each
  cell of the tape. (It can overwrite the input, once per cell.
  Remember that at the beginning of computataion, the tape after the
  input is assumed to be filled with spaces.)

  Be sure to explain the structure and operation of your
  machine. 
\end{problem}

\begin{solution}
  Your solution goes here.
\end{solution}

\begin{problem}
\textbf{[Turing Machine Variants]} Problem 3.10. (Hint: you can assume
that there exists a Turing machine that can calculate the function of
Problem 1, even if you couldn't specify it yourself.)
\end{problem}

\begin{solution}
  Your solution goes here.
\end{solution}

\begin{problem}
\textbf{[Enumerators]} Problem 3.16
\end{problem}

\begin{solution}
  Your solution goes here.
\end{solution}

\begin{problem}
  \textbf{[Non-Determinism, Decidibility]} Problem 3.3
\end{problem}

\begin{solution}
  Your solution goes here.
\end{solution}


\end{document}

%%% Local Variables: 
%%% mode: latex
%%% TeX-master: t
%%% End: 
