\documentclass{article}

\input{6045preamble}
\usepackage{amsmath}

\begin{document}

\homework{3}{Prof. Ron Rivest}{Due: 12 March 2003}{}

\begin{problem}
Show that the following language is Turing decidable:

\begin{eqnarray*}
     L = \{ c w c  & | &    w \text{ is a string in } \{a,b\}^* \text{ that is} \\
                   &   &    \text{well-formed if a is read as a "left parenthesis"} \\
                   &   &    \text{and b is read as a "right parenthesis".} \} \\
\end{eqnarray*}
thus  $cabc$ and $caababbc$ are in $L$, 
while $cbac$ and $caabbba$ is not. 

One acceptable solution to this problem is to state $\Sigma$ and $\Gamma$
and draw a complete transition function diagram for this Turing Machine.
Another acceptable solution to this problem is to state $\Sigma$ and $\Gamma$
and provide "pseudocode"
for your procedure that is sufficiently detailed that the grader
is convinced you could have written out the transition function
diagram correctly.
\end{problem}

\begin{problem}
Show that the collection of decidable languages is closed under the following
operations: (Sipser 1.14)
\begin{enumerate}
\item Union
\item Concatenation
\item Star
\item Complementation
\item Intersection
\end{enumerate}
\end{problem}

\begin{problem}
Consider a Turing Machine whose tape is a two-dimensional array of cells with
a single read/write head. (Think of it as the first quadrant of the
x-y plane where each cell on the tape is identified with a pair of positive
integers $(x,y)$). The head begins in the the lower left hand corner
of the array (which we think of as the cell, $(1,1)$) and at each step in
the computation the machine can move the move the head Left, Right, Up or Down.
(That is, the transition function maps 
$Q \times \Gamma \leftarrow Q \times \Gamma \times \{L,R,U,D\}$. 
It is considered a no-op if the machine attempts to move the read/write 
head to the left of the starting cell or below the starting cell). 
Prove that this
machine is equivalent to a standard Turing Machine.
\end{problem}


\end{document}