%\documentstyle[10pt,twoside]{article}
\documentstyle[twoside, 11pt]{article}
\setlength{\oddsidemargin}{0.25 in}
\setlength{\evensidemargin}{-0.25 in}
\setlength{\topmargin}{-0.6 in}
\setlength{\textwidth}{6.5 in}
\setlength{\textheight}{8.5 in}
\setlength{\headsep}{0.75 in}
\setlength{\parindent}{0 in}
\setlength{\parskip}{0.1 in}

%
% The following commands sets up the lecnum (lecture number)
% counter and make various numbering schemes work relative
% to the lecture number.
%
\newcounter{lecnum}
\renewcommand{\thepage}{\thelecnum-\arabic{page}}
\renewcommand{\thesection}{\thelecnum.\arabic{section}}
\renewcommand{\theequation}{\thelecnum.\arabic{equation}}
\renewcommand{\thefigure}{\thelecnum.\arabic{figure}}
\renewcommand{\thetable}{\thelecnum.\arabic{table}}

%
% The following macro is used to generate the header.
%
\newcommand{\problemset}[3]{
   \pagestyle{myheadings}
   \thispagestyle{plain}
   \newpage
   \setcounter{lecnum}{#1}
   \setcounter{page}{1}
   \noindent
   \begin{center}
   \framebox{
      \vbox{\vspace{2mm}
    \hbox to 6.28in { {\bf CS~21~~~Decidability and Tractability
                        \hfill Winter 2012} }
       \vspace{4mm}
       \hbox to 6.28in { {\Large \hfill Problem Set #1  \hfill} }
       \vspace{2mm}
       \hbox to 6.28in { {\it Out: #2 \hfill Due: #3} }
      \vspace{2mm}}
   }
   \end{center}
   \vspace*{4mm}
}

%
% Convention for citations is authors' initials followed by the year.
% For example, to cite a paper by Leighton and Maggs you would type
% \cite{LM89}, and to cite a paper by Strassen you would type \cite{S69}.
% (To avoid bibliography problems, for now we redefine the \cite command.)
%
\renewcommand{\cite}[1]{[#1]}

\input{epsf}

%Use this command for a figure; it puts a figure in wherever you want it.
%usage: \fig{NUMBER}{FIGURE-SIZE}{CAPTION}{FILENAME}
\newcommand{\fig}[4]{
            \vspace{0.2 in}
            \setlength{\epsfxsize}{#2}
            \centerline{\epsfbox{#4}}
            \begin{center}
            Figure \thelecnum.#1:~#3
            \end{center}
    }

% Use these for theorems, lemmas, proofs, etc.
\newtheorem{theorem}{Theorem}[lecnum]
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{claim}[theorem]{Claim}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{definition}[theorem]{Definition}
\newenvironment{proof}{{\bf Proof:}}{\hfill\rule{2mm}{2mm}}

% Some useful equation alignment commands, borrowed from TeX
\makeatletter
\def\eqalign#1{\,\vcenter{\openup\jot\m@th
  \ialign{\strut\hfil$\displaystyle{##}$&$\displaystyle{{}##}$\hfil
      \crcr#1\crcr}}\,}
\def\eqalignno#1{\displ@y \tabskip\@centering
  \halign to\displaywidth{\hfil$\displaystyle{##}$\tabskip\z@skip
    &$\displaystyle{{}##}$\hfil\tabskip\@centering
    &\llap{$##$}\tabskip\z@skip\crcr
    #1\crcr}}
\def\leqalignno#1{\displ@y \tabskip\@centering
  \halign to\displaywidth{\hfil$\displaystyle{##}$\tabskip\z@skip
    &$\displaystyle{{}##}$\hfil\tabskip\@centering
    &\kern-\displaywidth\rlap{$##$}\tabskip\displaywidth\crcr
    #1\crcr}}
\makeatother

% **** IF YOU WANT TO DEFINE ADDITIONAL MACROS FOR YOURSELF, PUT THEM HERE:



\begin{document}
\problemset{3}{January 25}{\bf {February 1}}

Reminder: you are encouraged to work in groups of two or three;
however you must turn in your own write-up and note with whom you
worked. You may consult the course notes and the text (Sipser).
Please attempt all problems. {\bf To facilitate grading, please
turn in each problem on a separate sheet of paper and put your
name on each sheet. Do not staple the separate sheets.}

\begin{enumerate}
\item Here is an informal description of a 2-Stack
Nondeterministic Pushdown Automata (2-NPDA): the machine is just
like an ordinary NPDA, except there is a second stack that behaves
just like the first. At each step, the machine reads a symbol from
the tape (possible $\epsilon$), pops specified symbols from each
of the two stacks (either may be $\epsilon$), pushes specified
symbols onto each of the two stacks (either may be $\epsilon$),
and moves into a specified state. The machine accepts if there is
some computation on its input string that causes it to reach an
accept state.

\begin{enumerate}
\item Give a formal definition of a 2-NPDA, and a formal
definition of what it means for a 2-NPDA to accept an input
string. Your definition will probably begin with something like
``A 2-NPDA is a 7-tuple...''

\item Give an informal description of a 2-NPDA that decides the
language:
\[L = \{a^nb^nc^n: n \ge 0\}.\]

\item Prove that 2-NPDAs are equivalent to Turing Machines. That
is, show language $L$ is decided by a 2-NPDA if and only if it is
decided by a Turing Machine.
\end{enumerate}

\item Here is an informal description of a Queue Automaton: the
machine is similar to an NPDA, except that the stack (``last in,
first out'' memory) is replaced with a queue (``first in, first
out'' memory). At each step, the machine reads a symbol from the
tape (possible $\epsilon$), dequeues a specified symbol (possibly
$\epsilon$) from the head of the queue, enqueues a specified
symbol onto the tail of the queue (possibly $\epsilon$), and moves
into a specified state. The machine accepts if there is some
computation on its input string that causes it to reach an accept
state.

\begin{enumerate}
\item Give a formal definition of a Queue Automaton, and a formal
definition of what it means for a Queue Automaton to accept an
input string. Your definition will probably begin with something
like ``A Queue Automaton is a 6-tuple...''

\item Prove that Queue Automata are equivalent to Turing Machines.
That is, show language $L$ is decided by a Queue Automaton if and
only if it is decided by a Turing Machine. Hint: repeated pairs of
``dequeue $x$'' and ``enqueue $x$'' operations cyclically shift
the queue in one direction. Can you use a sequence of cyclic
shifts to replace the symbol at the head of the queue? Can you use
a sequence of cyclic shifts to effect a cyclic shift in the {\em
other} direction? For this last part you may want a queue alphabet
that contains all {\em pairs} of symbols from the input alphabet.
\end{enumerate}


\item
$[$worth 6 pts$]$ This problem concerns that language TILE, defined as
follows. Informally, an instance is a collection of $k$ {\em tile types}, together with a list of {\em horizontally
compatible} pairs of tile types, and a list of {\em vertically
compatible} pairs of tile types. An $n \times n$ {\em tiling} is a
placement of tiles into an $n \times n$ grid, so that every pair
of horizontally adjacent tiles is horizontally
compatible, and every pair of vertically adjacent tiles
is vertically compatible; in addition we
require that the tile in the upper left corner is tile type $1$. The
language TILE consists of all those instances for which there exists
an $n \times n$ tiling for all $n \ge 0$.

Formally, the language TILE is the set of those tuples \[\langle
k, H \subseteq [k] \times [k], V \subseteq [k] \times [k] \rangle\] for which the following holds. For all $n \ge 0$
there exists a function $f:[n]\times[n] \rightarrow [k]$ for
which:
\begin{itemize}
\item $f(1,1) = 1$, and

\item $(f(x, y), f(x, y+1)) \in H$ for all $1 \le x \le n$, and $1 \le y \le n-1$,
and

\item $(f(x, y), f(x+1, y)) \in V$ for all $1 \le x \le n-1$ and $1 \le y \le n$.
\end{itemize}

Here, $[n]$ is shorthand for the set $\{1,2,3,\ldots, n\}$. Prove
that TILE is undecidable by giving a many-one reduction from
$\overline{\mbox{HALT}}$ (the complement of the language HALT).
Hint: it will be helpful to ``name'' some of your tiles with
triplets of symbols.


\item Prove that a language $L$ is RE if and only if it can be
expressed as
\[L = \{x : \mbox{there exists $y$ for which } \langle x,y\rangle \in R\}\]
where $R$ is a decidable language. In other words, you must prove
that every language of this form is RE, and that every RE language
$L$ has a related decidable language $R_L$ that allows it to be
described in the form above.



\end{enumerate}


\end{document}