\documentclass{article}

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

\begin{document}

\homework{7}{Nancy Lynch}{Due: Monday, April 2}{Elena Grigorescu}

\bigskip
{\bf Readings:} Handout 6 (from Hopcroft book); Section 5.3; Problems
5.28-5.30.

\bigskip

\begin{problem} 


(Counter Machine Examples) \\
Informally but clearly describe counter machines that recognize the
following languages.  Use as few counters as you can.  (You may assume
that a special endmarker appears at the end of the input string.)
\begin{enumerate}
\item
$\{ a^i b^j | i \leq j \}$.
\item
$\{ a^i b^j c^k | i \leq j \leq k \}$.
\item
$\{ a^i b^j c^k | k = i j \}$.
\end{enumerate}
\end{problem}

\begin{problem} 
(Counter Machine Simulation of Stack Machine)\\
Suppose we design a counter machine to simulate a $k$-stack
machine, using the same strategy discussed in lecture for simulating
$2$ stacks with $3$ counters.
\begin{enumerate}
\item
How many counters does this require?  Why?

\item
Simulating a single step of the $k$-stack machine requires that the
CM (Counter Machine) emulate the reading of the top symbol of each stack,
without removing that symbol from the stack.
Describe clearly how the CM can read the top symbol of a stack.
\item
Before the CM can determine the stack machine transition to be
emulated, it must know the top symbol of every stack.  Describe how
the CM can remember these symbols in a way that allows it to determine
the next stack machine transition.
\item
After the CM determines the stack machine transition to be simulated,
it must modify the simulated stacks as specified by that transition.
Describe clearly how the CM can do this.  How can it keep track of its
progress?
\item
How does the CM simulate the state change of the simulated stack
machine?
%
\end{enumerate}
\end{problem}


\begin{problem} 
(Mapping Reducibility) \\
Define {\em Total} to be the language $\{ <M> |~M \mbox{ is a Turing
machine and } L(M) = \{ 0, 1 \}^* \}$, that is, the set of
representations of (basic) Turing machines that accept all strings of
$0$s and $1$s.
Use mapping reducibility to prove the following statements.
Cite explicitly any theorems about mapping reducibility that you use.
\begin{enumerate}
\item
The complement of {\em Total\/} is not Turing-recognizable.
\item
{\em Total} is not Turing-recognizable.
\end{enumerate}
\end{problem}

\begin{problem} 
(Rice's Theorem Applications)\\
Which of the following are decidable and which are undecidable?  Give
proofs.  Use Rice's Theorem wherever you can, in showing
undecidability.
\begin{enumerate}
\item
$\{ <M> |~M$ is a Turing machine and $M$ has more than 75 states$\}$.
\item
$\{ <M> |~M$ is a Turing machine and $L(M)$ is recognized by some Turing
machine $M'$ with more than 75 states$\}$.
\item
$\{ <M> |~M$ is a Turing machine and $L(M)$ is recognized by some Turing
machine $M'$ with at most 75 states and whose tape alphabet contains only five symbols$\}$.

\item
$\{ <M> |~M$ is a Turing machine that accepts every even-length string (and
possibly other strings)$\}$.

\item
$\{ <M_1,M_2> |~M_1 \mbox{ and } M_2 \mbox{ are Turing machines and } 
               L(M_1) \cap L(M_2) = \emptyset \}$.
\end{enumerate}
\end{problem}


\end{document}













