\documentclass{article}

\input{6045preamble}
\usepackage{amssymb,amsmath,graphicx}

\begin{document}

\homework{4}{Nancy Lynch}{Due: March 9, 2004}{Vinod Vaikuntanathan}

\noindent
\begin{problem} {\bf Detailed Turing machine description} \\
% (25 points)
Give a complete, formal description of a (basic one-head, one-tape)
Turing machine that {\em decides\/} the language 
$L = \{ 0^i 1^j 2^i: 0 \leq i < j \}$.
This should consist of a list of the tuple components of the Turing
machine, with the transition function represented by a state
transition diagram. \\
(Yes, we know that it's tedious to write Turing machine descriptions.
But we think that everyone should do it once.  We'll try to avoid
asking for this on other homeworks.)
\end{problem}

\noindent
\begin{problem} {\bf Implementation-Level (also known as
``higher-level'' Turing machine description} \\
% (20 points)
Describe the operation of a basic Turing machine that {\em
recognizes\/} the language 
$$L = \{ w : w \mbox{ does not contain twice
as many 0s as 1s} \}$$
This time, your description should not be completely formal.  Rather,
it should consist of a list of the tuple components, with the
transitions described in words.  (This is what Sipser calls an
``implementation description'' on p. 157.)

You may describe your construction in terms of a variant of the basic
Turing machine model presented in class or in Sipser's book (e.g.,
multitape), provided that you quote the correct transformation result
to show how one would turn your construction into a description of a
basic Turing machine to recognize the same language.
\end{problem}

\noindent
\begin{problem} {\bf Robustness of the Turing Machine model} \\
Consider a Turing machine model that uses a 2-dimensional tape,
corresponding to the upper right quadrant of the plane. The head
of such a Turing machine
could move to the right, left, up or down.
Sketch a proof that such a model does not add extra computing power;
that is, the class of languages recognized by such Turing machines is
the same as the class recognized by basic Turing machines.

\end{problem}

\noindent
\begin{problem} {\bf Turing-recognizability and Turing-decidability} \\
%(25 points)
\begin{enumerate}
\item
Sketch proofs that the class of Turing-recognizable languages is
closed under the language operations union, intersection,
concatenation, and star.
\item
Sketch proofs that the class of Turing-decidable languages is closed
under the language operations union, intersection, complement,
concatenation, and star.
\end{enumerate}
\end{problem}

\noindent
\begin{problem}
\begin{enumerate}
\item
Let $L$ be a set of natural numbers that can be enumerated by an
enumerator Turing machine in nondecreasing order, possibly with
repeats.
Prove that $L$ is a decidable set of numbers.
\end{enumerate}
\end{problem}

\end{document}