\documentstyle[6.045-ps,12pt]{article}

\name{Marc Horowitz}
\psnum{5}
\duedate{Friday, March 15}
\section{Bronwyn Eliot, Thursday 1pm}
\handoutnum{17}

\begin{document}

\problem{1}{Turing Machine Operation}

If $n$ is even, the machine will halt in the configuration
$(h,(\#a)^{n/2+1})$.  If $n$ is odd, the machine will never halt.  It
will hang in the configuration $(q_0,\#(\#a)^{(n+1)/2})$.


\problem{2}{Designing a Turing Machine}

$
\def\sp{\hspace{0.4in}}
\def\s{\sigma}
\def\N{\fbox{N}}
\def\Y{\fbox{Y}}
\catcode`\^^I=4%
\begin{array}{l@{\sp}ll@{\sp}l} \hline
q	\s_1	\s_2	\delta(q,\s_1,\s_2) \\ \hline
q_0	\#	\#	(q_1,L,\#) \\
q_1	0	\#	(q_1,L,\#) \\
q_1	1	\#	(q_1,L,\#) \\
q_1	\#	\#	(q_2,R,L) \\
q_2	0	0	(q_2,R,L) \\
q_2	1	1	(q_2,R,L) \\
q_2	0	1	(q_3,R,L) \\
q_2	1	0	(q_3,R,L) \\
q_2	\#	\#	(q_6,L,\#) \\
q_3	0	0	(q_3,R,L) \\
q_3	1	1	(q_3,R,L) \\
q_3	0	1	(q_3,R,L) \\
q_3	1	0	(q_3,R,L) \\
q_3	\#	\#	(q_4,L,\#) \\
q_4	0	\#	(q_4,L,\#) \\
q_4	1	\#	(q_4,L,\#) \\
q_4	\#	\#	(q_5,\N,\N) \\
q_5	\N	\N	(h,R,R) \\
q_6	0	\#	(q_6,L,\#) \\
q_6	1	\#	(q_6,L,\#) \\
q_6	\#	\#	(q_7,\Y,\Y) \\
q_7	\Y	\Y	(h,R,R) \\ \hline
\end{array}\)

\end{document}
