\documentclass{article}
\input{6840-preamble}

\begin{document}
\psetnum{3}
\date{2004/10/21}

\begin{pset}

  \begin{problem}
    Let $L$ be the language of all Turing machine representations that
    contain no useless states. We will show that $L$ is
    undecidable. We begin with a lemma.

    \begin{lemma}
      Any Turing machine can be converted to a Turing machine that
      accepts the same language and either has no useless states, or
      the only useless state is the accept state.
    \end{lemma}
    \begin{proof}
      Suppose $M$ is a Turing machine that accepts some language
      $L_M$. We construct a Turing machine $M'$ that accepts $L_M$ and
      satisfies the useless-state property described above. We begin
      by making $M'$ a copy of $M$; clearly, it therefore accepts
      $L_M$.

      We augment the input alphabet of $M'$ with an additional symbol
      $\wr$. Let $S$ be the set of states of $M$, except for the
      accept state $q_{\text{accept}}$. Put $S$ in any order. We add
      transitions to $M'$ such that if $\wr$ is the current tape
      symbol, the machine moves from the current state to the next
      state in the ordering of $S$ (or back to the first state in the
      ordering if the current state was the last state in the
      ordering), without moving the tape head.

      The result of this construction is a machine $M'$ that has the
      same states as $M$, and accepts the same language $L_M$, since
      we did not change any of the transitions except for those
      involving our new symbol. Moreover, if the input string is
      simply the symbol $\wr$, then $M'$ will loop through all states
      except for $q_{\text{accept}}$. This ensures that all states
      except $q_{\text{accept}}$ are non-useless. This proves the
      lemma.
    \end{proof}

    We now prove by contradiction that $L$ is undecidable. Suppose $L$
    is decidable, and $R$ is a $\TM$ that decides $L$. We give a
    machine $\aleph$ that solves $A_\TM$.

    \begin{turing}{$\aleph$}{On input $\tup{M,w}$,}
    \item Construct the Turing machine $\mathscr{M}$ that ignores its
      input and simulates $M$ on $w$.
    \item Construct the Turing machine $\mathfrak{M}$ that accepts the
      same language as $\mathscr{M}$ and either has no useless states,
      or the only useless state is the accept state, as described above.
    \item Run $R$ on $\mathfrak{M}$. If $\mathfrak{M}$ has any useless
      states, the useless state is $q_{\text{accept}}$, so $M$ does
      not accept $w$. So \textit{reject}. If $\mathfrak{M}$ has no useless
      states, $M$ accepts $w$. So \textit{accept}.
    \end{turing}

    $\aleph$ decides $A_\TM$. But $A_\TM$ is undecidable. This is a
    contradiction $\nleftrightarrow$. So $L$ is undecidable.
  \end{problem}

  \begin{problem}
    Let $L$ be any Turing-recognizable language. We show that $L$ is
    mapping reducible to $A_\TM$. Let $M$ be a recognizer for $L$.

    Define $f(w) = \tup{M,w}$. Then $f$ maps $L$ to $A_\TM$: if $w$ is
    in $L$, then $M$ accepts $w$, and so $\tup{M,w}$ is in $A_\TM$;
    conversely, if $w$ is not in $L$, then $M$ does not accept $w$,
    and so $\tup{M,w}$ is not in $A_\TM$.

    To see
    that $f$ is a computable function, consider the following machine
    that generates $f$:

    \begin{turing}{F}{On input $w$,}
    \item Output $\tup{M,w}$
    \end{turing}
  \end{problem}

  \begin{problem}
    Let $BB(k)$ be the busy beaver function. We show that $BB(k)$ is
    not computable. Suppose it is. Then there is a machine
    $\mathfrak{B}$ that computes $BB(k)$. Assume without loss of
    generality that $\mathfrak{B}$ produces its output in a unary
    representation (if it does not, we can create a new machine that
    simulates $\mathfrak{B}$ and then converts the output to unary).

    Then we create the following machine:

    \begin{turing}{$M$}{On a blank tape,}
    \item Obtain own description $\tup{M}$ via the recursion
      theorem. Let $x$ be the number of states in $\tup{M}$.
    \item Compute $BB(x)$ by simulating $\mathfrak{B}$ on input $x$,
      and write the (unary) result to the tape.
    \item Write an additional \texttt{1} to the tape, then halt.
    \end{turing}

    Note that $M$ is a Turing machine with $x$ states. It outputs
    $BB(x)+1$ \texttt{1}s to the tape, since the unary representation
    of $BB(x)$ is simply $BB(x)$ \texttt{1}s. But $BB(x)$ is defined
    to be the maximum number of \texttt{1}s producible by a $x$-state
    $\TM$. This is a contradiction $\nleftrightarrow$. So $BB$ is
    uncomputable.
  \end{problem}

  \begin{problem}
    Let $AMBIG_\CFG$ be the ambiguity problem for $\CFG$s. We show
    that $AMBIG_\CFG$ is undecidable by reduction from $PCP$. Let
    \[P =
    \set{\left[\frac{t_1}{b_1}\right],\left[\frac{t_2}{b_2}\right],\ldots,\left[\frac{t_k}{b_k}\right]}
    \]
    be a $PCP$ instance. Define $G$ to be a $\CFG$ over the terminal
    symbols $\cset{t_i, b_i, a_i}{1 \le 1 \le k}$ as follows
    \[
    G =
    \begin{cases}
      S \to T | B\\
      T \to t_1 T a_1 | \cdots | t_k T a_k | t_1a_1 | \cdots |t_k
      a_k\\
      B \to b_1 B a_1 | \cdots | b_k B a_k | b_1 a_1 | \cdots | b_k
      a_k
    \end{cases}
    \]
    
    We show that $G$ is ambiguous if and only if $P$ is solvable.

    Suppose $P$ is solvable. Then there is a sequence of dominoes
    $i_1, i_2, \ldots, i_n$ such that \[t_{i_1} t_{i_2} \cdots t_{i_n}
    = b_{i_1} b_{i_2} \cdots b_{i_n}\] Consider the string $t_{i_1}
    t_{i_2} \cdots t_{i_n} a_{i_n} a_{i_{n-1}} \cdots a_{i_1}$. This
    string can be derived in the $\CFG$ $G$ by repeatedly applying the
    $T$ production rule. However, since the string is equal to $b_{i_1}
    b_{i_2} \cdots b_{i_n} a_{i_n} a_{i_{n-1}} \cdots a_{i_1}$, it can
    also be generated by repeatedly applying the $B$ production
    rule. This gives two different parse trees, so $G$ is ambiguous.

    Next, suppose $G$ is ambiguous. We show that $P$ is solvable.
    Since $G$ is ambiguous, there is some string $s$ that has two
    different parse trees. Observe that $s$ must end in some sequence
    of $a$ symbols equal in length to the number of non-$a$ symbols
    before it; write it as $a_{i_n} a_{i_{n-1}} \cdots a_{i_1}$.

    Note that, if we consider the $T$ production rule alone as a
    grammar, it is unambiguous, since for a given string, there is
    only one clause in the rule that can be used to parse it: the one
    corresponding to the $a_i$ at the end of the string. The same is
    true of the $B$ production rule. Because of this, one of the parse
    trees for $s$ must use the $T$ production rule and the other must
    use the $B$ production rule. So, using the two parse trees, $s$
    can be written as either $t_{i_1} t_{i_2} \cdots t_{i_n} a_{i_n}
    a_{i_{n-1}} \cdots a_{i_1}$ or $b_{i_1} b_{i_2} \cdots b_{i_n}
    a_{i_n} a_{i_{n-1}} \cdots a_{i_1}$. This means that
    \[t_{i_1} t_{i_2} \cdots t_{i_n} = b_{i_1} b_{i_2} \cdots
    b_{i_n}\] and so $i_1, i_2, \ldots, i_n$ is a solution to the PCP.

    We have shown that $PCP$ is reducible to $AMBIG_\CFG$. So there
    can be no $\TM$ that decides $AMBIG_\CFG$, since such a machine
    would also be able to decide $PCP$, which is undecidable.
  \end{problem}

  \begin{problem}
    \newcommand{\tDFA}{\ensuremath{\mathsf{2DFA}}}
    \begin{subproblem}
      Let $A_{\tDFA}$ be the acceptance problem for two-headed finite
      automata. We show that $A_{\tDFA}$ is decidable.

      Note that a $\tDFA$ can be simulated by a Turing machine. We
      quadruple the size of the input alphabet by
      two mark bits, one representing the position of each head. Then
      the $\TM$ can scan back and forth to find the mark bits and
      identify the symbols under each head in the $\tDFA$. It can then
      move the mark bits to an adjacent symbol in order to simulate a
      transition.

      In order to show that $A_\tDFA$ is recognizable, we also need to
      show that the number of configurations of a $\tDFA$ is
      bounded.
      
      \begin{lemma}
        A $\tDFA$ with $q$ states has $q(n+2)^2$ possible
        configurations on an input of length $n$.
      \end{lemma}

      \begin{proof}
        Since the input has length $n$, the tape of the $\tDFA$
        has length exactly $n+2$. Therefore, there are $n+2$ possible
        positions for each of the two heads, and $q$ states. The state
        the $\tDFA$ is in and the position of each head defines a
        configuration, since the tape's contents are static.
      \end{proof}

      This gives us a procedure for deciding $A_\tDFA$. The following
      $\TM$ $M$ decides $A_\tDFA$:

      \begin{turing}{$M$}{On input $\tup{D,w}$, where $D$ is a $\tDFA$
          and $w$ an input string,}
      \item Write $w$ and the two delimiter characters to the tape,
        placing both mark bits at the leftmost symbol in $w$
      \item Simulate $D$ on $w$ for at most $q(n+2)^2$ transitions, or
        until it halts
      \item If $D$ accepts, \textit{accept}. If $D$ rejects or does
        not halt, \textit{reject}.
      \end{turing}
    \end{subproblem}
    \vspace{2em}
    \begin{subproblem}
      Let $E_{\tDFA}$ be the emptiness problem for two-headed finite
      automata. We show that $E_{\tDFA}$ is undecidable. We do so by
      showing that for a $\TM$ $M$, we can create a $\tDFA$ $D_{M,w}$ that
      verifies a $\TM$ computation history for $M$ on input $w$ and accepts if it
      is a valid accepting computation history.

      The procedure for doing so is essentially identical to the
      procedure for doing so with a $\LBA$ (Sipser, proof of theorem
      5.9), except that we use the second head instead of marking
      the tape in verifying the configuration transitions.

      \begin{turing}{$\tDFA\;\;\;D_{M,w}$}{On input $C =
          \#C_1\#C_2\#\cdots\#C_l\#$,}
      \item Using the first head, verify that $C_1$ is the start
        configuration for $M$ on $w$
      \item Using the first head, verify that $C_l$ is an accept
        configuration for $M$.
      \item For each $i$ from $1$ to $l-1$, verify the transition from
        configuration $i$ to $i+1$:
        \vspace{-1.5em}
        \begin{enumerate}
          \setlength{\itemsep}{-\parsep}
        \item Scan to the beginning of configuration $i$ with the
          first head and the beginning of configuration $i+1$ with the
          second head.
        \item Scan over $C_i$ and $C_{i+1}$ with the two heads in
          lockstep, and verify that all tape symbols are identical
          except for those under or next to $M$'s head in $C_i$.
        \item Verify that $C_{i+1}$ is a valid configuration
          transition from $C_{i}$ by checking that the state, head
          position, and symbol under the head were updated according
          to the transition function of $M$.
        \end{enumerate}
      \item If all of these conditions are met, \emph{accept}.
        Otherwise, \emph{reject}.
      \end{turing}

      Now assume that $E_\tDFA$ is decidable by a machine $R$. We give
      the following $\TM$ $\aleph$ that decides $A_\TM$:
      
      \begin{turing}{$\aleph$}{On input $\tup{M,w}$,}
      \item Generate the $\tDFA$ $D_{M,w}$ that verifies accepting
        computation histories for $M$ on $w$.
      \item Simulate $R$ on $D_{M,w}$
      \item If $R$ accepts, then \textit{reject}. Otherwise, \textit{accept}.
      \end{turing}

      $\aleph$ accepts on $\tup{M,w}$ only if there is a valid
      accepting computation history for $M$ on $w$, i.e. if $A_\TM$
      accepts, and rejects otherwise. But $A_\TM$ is undecidable. This
      is a contradiction $\nleftrightarrow$. So $E_\tDFA$ is undecidable.
    \end{subproblem}
  \end{problem}
  
  \begin{problem}
    The following program, written in Scheme, produces itself as output.
    
    \begin{lstlisting}[language=Scheme]
      ((lambda (x) (list x (list (quote quote) x)))
       (quote (lambda (x) (list x (list (quote quote) x)))))
    \end{lstlisting}

    The output of this program produced by running it through the MIT
    Scheme interpreter is below. (It is also above!)

    \begin{lstlisting}[language=Scheme]
      ((lambda (x) (list x (list (quote quote) x)))
       (quote (lambda (x) (list x (list (quote quote) x)))))
    \end{lstlisting}
  \end{problem}

  \begin{problem}
    On the universe of real numbers $\R$, a model for the
    relation $\phi_\text{lt}$ is
    \[ \phi_\text{lt}(x,y) = \text{\textsc{true}} \text{  if  } x < y \]
    Call this model $(\R, <)$.
    
    Recall that $\phi_{\text{eq}}$ is the three conditions of an
    equivalence relation; on $\R$, the standard equality
    relation satisfies $\phi_{\text{eq}}$. So the first condition
    holds. The second condition holds because $x = y$ implies $x \not
    < y$. If $x \neq y$, then either $x < y$ or $y < x$, so the third
    condition holds. The fourth condition is transitivity: if $x < y$
    and $y < z$, then $x < z$; this also holds under $(\R, <)$. The
    final condition states that for every $x$ there exists some $y <
    x$; this is true in $\R$. So the model $(\R, <)$ satisfies the
    statement $\phi_\text{lt}$.
    
  \end{problem}
\end{pset}

\end{document}