\documentstyle[11pt]{article}
% frob with the margins
\addtolength{\topmargin}{-1in}
\addtolength{\footskip}{-1in}
\addtolength{\textheight}{2in}
\addtolength{\oddsidemargin}{-.5in}
\addtolength{\evensidemargin}{-.5in}
\addtolength{\textwidth}{1in}
% no page numbers
\pagestyle{empty}
% counter for page numbers
\newcounter{pg}
\setcounter{pg}{2}

% DEFINE THE PROBLEM SET NUMBER
\def\psnum{5}

% DEFINE THE DUE DATE
\def\due{March 15, 1991}

% title command
\newcommand{\mytitle}{{\large\noindent 6.045/18.400 Automata,
Computability, and Complexity \hfill{} Juliet Bourne \\
Problem Set \psnum \hfill{} \due \\}
\vspace{-.6in}
\begin{center} \rule{6in}{.25mm} \end{center}}
% newpage setup command 
\newcommand{\mypage}[1]{\newpage{\large\noindent 6.045/18.400 Automata,
Computability, and Complexity \hfill{} Juliet Bourne \\
Problem Set \psnum \hfill{} \due \\}
\vspace{-.6in}
\begin{center} \rule{6in}{.25mm} \end{center}}
%\newcommand{\mynewpage}{\newpage\noindent
%{\large 6.045/18.400 \hfill{} Juliet Bourne \\
%Problem Set \psnum \hfill{} {\bf Page \thepg} \\}
%\vspace{-.6in}
%\begin{center}
%\rule{6in}{.25mm}
%\end{center}
%\addtocounter{pg}{1}}
% problem command
\newcommand{\prob}[1]{\noindent{\fbox{\large\bf Problem #1}}\vspace{.25in}}
% subproblem command
\newcommand{\subprob}[1]{\vspace{.15in} \noindent{\large\bf #1.}}
% equations commands
\newcommand{\beq}{\vspace*{-.3in}\begin{eqnarray*}}
\newcommand{\eeq}{\end{eqnarray*}}

\newcommand{\bea}{\begin{center}$\begin{array}}
\newcommand{\eea}{\end{array}$\end{center}\vspace*{.2in}}
\newcommand{\un}{\underline}

\begin{document}

\mytitle

\prob{1: Turing Machine Operation}

\noindent Let M be a Turing machine such that:

\beq
M & = & (K, \Sigma, \delta, s) \\
K & = & \{q_0,q_1,q_2\} \\
s & = & q_0 \\
\Sigma & = & \{a,\#\} 
\eeq

\bea{ccc}\hline
q & \sigma & \delta(q,\sigma) \\ \hline
q_0 & a & (q_1,L) \\
q_0 & \# & (q_0,\#) \\ \hline
q_1 & a & (q_2,\#) \\
q_1 & \# & (h,\#) \\ \hline
q_2 & a & (q_2,a) \\
q_2 & \# & (q_0,L)
\eea

\beq
n = 0 & \Rightarrow & (q_0,\#\un{a}) \vdash (q_1,\un{\#}) \vdash
(h,\un{\#}) \\
n = 1 & \Rightarrow & (q_0,\#a\un{a}) \vdash (q_1,\#\un{a}) \vdash
(q_2,\#\un{\#}) \vdash (q_0,\un{\#}) \vdash (q_0,\un{\#}) \vdash ... \\
n = 2 & \Rightarrow & (q_0,\#aa\un{a}) \vdash (q_1,\#a\un{a}) \vdash
(q_2,\#a\un{\#}) \vdash (q_0,\#\un{a}) \vdash (q_1,\un{\#}) \vdash
(h,\un{\#})
\eeq

Therefore, if $n$ is even, then $M$ will accept the input abd halt. If
$n$ is odd, then $M$ will hang. $M$ accepts strings of a's of odd
length.

\mypage

\prob{2: Designing a Turing Machine}

\noindent Design a Turing machine to accept the following languages:

\subprob{a} $\{ww^R : w \in \{0,1\}^*\}$

\noindent Steps:

\begin{enumerate}
\item Move left. Read symbol. If it is marked or \# , then done. If not,
mark and remember it.
\item Scan left for \# or marked symbol.
\item Move right. Read and compare symbol to remembered symbol. If it
matches, then mark it.
\item Scan right for marked symbol. Go to 1.
\end{enumerate}

\beq
M & = & (K, \Sigma, \delta, s) \\
K & = & \{q_s, q_{0-scan}, q_{1-scan}, q_{0-comp}, q_{1-comp},
q_{pre-scan}, q_{scanR}, q_{scanL}, q_{cleanup} \} \\
\Sigma & = & \{0, 1, 0', 1', \#\} \\
s & = & q_s
\eeq

$\delta$:

\bea{ccc|ccc}\hline
q & \sigma & \delta(q,\sigma) & q & \sigma & \delta(q,\sigma) \\ \hline
q_s & 0 & (q_{0-scan},0') & q_{pre-scan} & 0',1' & (q_{scanR},R) \\
q_s & 1 & (q_{1-scan},1') & q_{pre-scan} & \#,0,1 & arbitrary \\ \cline{4-6}
q_s & 0',1' & (q_{scanL},L) & q_{scanR} & 0, 1 & (q_{scanR},R) \\
q_s & \# & (q_s,L) & q_{scanR} & \#,0',1' & (q_s,L) \\ \hline
q_{0-scan} & \#,0',1' & (q_{0-comp},R) & q_{scanL} & 0',1' & (q_{scanL},L) \\
q_{0-scan} & 0,1 & (q_{0-scan},L) & q_{scanL} & 0,1 & arbitary \\ \cline{1-3}
q_{1-scan} & \#,0',1' & (q_{1-comp},R) & q_{scanL} & \# &
(q_{cleanup},R) \\ \cline{4-6}
q_{1-scan} & 0,1 & (q_{1-scan},L) & q_{cleanup} & 0,1 & (q_{cleanup},R)
\\ \cline{1-3}
q_{0-comp} & 0 & (q_{pre-scan},0') & q_{cleanup} & 0' & (q_{cleanup},0) \\
q_{0-comp} & \#,1,0',1' & arbitrary & q_{cleanup} & 1' &
(q_{cleanup},1') \\ \cline{1-3}
q_{1-comp} & 1 & (q_{pre-scan},1') & q_{cleanup} & \# & (h,\#) \\
q_{1-comp} & \#,0,0',1' & arbitrary & \mbox{} & \mbox{} & \mbox{} \\ \hline
\eea

\mypage

\subprob{b} The set of strings in $\{0,1\}^*$ with an equal number of 0s
and 1s.

\noindent Steps:

\begin{enumerate}
\item Move left. Read symbol. If the symbol is not marked, then mark and
remember it. If symbol is marked, then scan left for unmarked symbol. If
none are found, then done. 
\item Scan left for \#.
\item Move right. Read symbol. If it is marked, then repeat 3. If it
is the opposite of the remembered symbol, then scan right for marked
symbol and goto 1.
\end{enumerate}

\beq
M & = & (K,\Sigma,\delta,s) \\
K & = & \{q_s, q_{scan-u}, q_{0-scan}, q_{1-scan}, q_{scanR}\} \\
\Sigma & = & \{0, 1, 0', 1', \#\} \\
s & = & q_s
\eeq

$\delta$:

\bea{ccc}\hline
q & \sigma & \delta(q,\sigma) \\ \hline
q_s & \# & (q_s,L) \\ 
q_s & 0 & (q_{1-scan},0') \\ 
q_s & 1 & (q_{0-scan},1') \\
q_s & 0',1' & (q_{scan-u},L) \\ \hline 
q_{0-scan} & 0 & (q_{scanR},0') \\
q_{0-scan} & 1,0',1' & (q_{0-scan},L) \\ 
q_{0-scan} & \# & arbitary \\ \hline
q_{1-scan} & 1 & (q_{scanR}, 1') \\
q_{1-scan} & 0,0',1' & (q_{1-scan},L) \\
q_{1-scan} & \# & arbitrary \\ \hline
q_{scanR} & 0,1,0',1' & (q_{scanR}) \\
q_{scanR} & \# & (q_{scan-u},L) \\ \hline
q_{scan-u} & 0 & (q_{1-scan},0') \\
q_{scan-u} & 1 & (q_{0-scan},1') \\
q_{scan-u} & 0',1' & (q_{scan-u},L) \\ 
q_{scan-u} & \# & (h,\#) \\ \hline
\eea

\mypage

\prob{3: Turing Machines as Binary Incrementors}

\noindent Construct a Turing machine to increment a binary number by one
and print the final answer.

\noindent Steps:

\begin{enumerate}
\item Move left. Read symbol. If it is 0, then change it to 1, move right,
and halt. If it is 1, then change it to 0 and repeat 1. If it is \#,
goto 2.
\item Move right. Write 1. Scan right for \#. Write 0. Move right and
halt.
\end{enumerate}

\beq
M & = & (K,\Sigma,\delta,s) \\
K & = & \{q_s, q_0, q_1, q_2, q_3, q_4\} \\
\Sigma & = & \{0, 1, \#\} \\
s & = & q_s
\eeq

$\delta$:

\bea{ccc}\hline
q & \sigma & \delta(q,\sigma) \\ \hline 
q_s & \# & (q_0,L) \\ \hline
q_0 & 0 & (q_3,1) \\
q_0 & 1 & (q_1,0) \\
q_0 & \# & (q_2,R) \\ \hline 
q_1 & 0 & (q_0,R) \\
q_1 & 1,\# & arbitrary \\ \hline 
q_2 & \# & (q_3,1) \\ 
q_2 & 0 & (q_4,1) \\
q_2 & 1 & arbitary \\ \hline
q_3 & 0,1 & (h,R) \\ 
q_3 & \# & arbitrary \\ \hline
q_4 & 0 & (q_4,R) \\
q_4 & \# & (q_3,0) \\
q_4 & 1 & arbitrary \\ \hline
\eea

\mypage

\prob{4: The Universality of Binary Alphabets}

For any Turing machine $M$ whose alphabet properly contains 0,1,\#,
there exists a Turing machine $M'$ whose alphabet is precisely
\{0,1,\#\} such that $M$ and $M'$ accept the same binary inputs. $M'$
can be created so that any of the other symbols in the alphabet of $M$
are simulated using only 0s, 1s, and \#s. For example, if the symbol $0'$
is used by $M$ as a marker to aid in computation, $\#10\#$ could be used
by $M'$ to simulate that marker. (The \#s separate markers from the rest
of the 0s and 1s.) In this way, all of the extra symbols that $M$ uses
to aid in its accepting of binary inputs can be simulated by just using
an alphabet of \{0,1,\#\}. Thus, $M'$ can be constructed to accept the
same binary inputs as $M$.

\mypage

\prob{5: TMs and PDAs}

Since any way of formalizing the idea of the ``computational procedure''
is equivalent to the idea of a Turing machine, if it can be shown that a
2-pda can simulate a Turing machine, then a 2-pda can accept anything
that a 3-pda or 4-pda, etc, can accept. 

A 2-pda can easily simulate a Turing machine. One stack is used for the
tape before where the head of the Turing machine would be and the other
for the rest of the tape. To set up the 2-pda to act like a Turing
machine, the input of the PDA would be pushed onto stack 2. Since the
input would be in reverse order on stack 2, each symbol of stack 2 would
be pushed onto stack 1. The input would then be in the correct order.
The head of the Turing machine would be simulated by the top of stack 2.
Whatever is at the top of stack 2 is what the head of the Turing machine
would be pointing at. To simulate moving left in the Turing machine, the
PDA would pop the top of stack 1 and push the popped symbol onto stack
2.  To simulate moving right, the PDA would pop the top of stack 2 and
push the popped symbol onto stack 1. To simulate writing a symbol in the
Turing machine, the PDA would just replace the top of stack 2 with
whatever symbol was to be written. When stack 1 is empty, it means that
the left end of the tape has been reached. When stack 2 is empty, it
means that the head of the Turing machine is currently looking at the
first blank of the infinite streams of blanks on the right side of the
tape. 

Thus, all of the operations and functionality of a Turing machine can be
simulated with a 2-pda. So, the 2-pda is as powerful as any other PDA
with more stacks.

\end{document}

