Recitation 5 latex source
This file is provided to help students create crib sheets
in latex if they wish. Some formatting was removed for clarity.
It is missing some macros, but you can figure out what they are
by looking at the pdf image. It is not a working latex file.
\huge{\textsc{18.404/6.5400 Recitation 5}}
This recitation covers configurations and the computation history method, with examples.
\section{TM Configurations}
A \textit{configuration} of a Turing machine (textbook p.168) completely represents the status of the TM. A configuration consists of the Turing machine's current:
\begin{itemize}[label=-]
\item state $q$ of the finite control,
\item location/position of the head $p$, and
\item tape contents $t$.
\end{itemize}
When writing out configurations as a string, we usually use a standard encoding. We write out the tape contents, then insert the state into the tape contents right before the symbol that the head is at. In other words, we use $uqv$, where $uv$ is the tape contents, $q$ is the state, and the head is currently at the first symbol of $v$. For example, if the tape contains the string \texttt{abcd}, the state of the machine is $q_{5}$, and the head is currently above \texttt{c}, we insert $q_{5}$ right before \texttt{c} to get the encoding \texttt{ab$q_{5}$cd}.
\subsection{Each configuration can only yield one next configuration}
Given a configuration of a deterministic $\mathsf{TM}$, we can always figure out what the next configuration will be. This is because a configuration contains all the inputs needed to calculate the transition function of the $\mathsf{TM}$. Specifically, if we initialize the Turing machine with the current configuration, then simulate one step, this gives the next configuration.
\subsection{\texorpdfstring{$A_{\mathsf{LBA}}$}{A\_LBA} is Decidable}
\textit{(textbook Theorem 5.9)} Let a \textit{linear bounded automaton} ($\mathsf{LBA}$) be a Turing machine which is not allowed to move its head off its input. Show that the language
\[A_{\mathsf{LBA}} = \{\left**|\text{ B is a $\mathsf{LBA}$ that accepts string $w$}\}\]
is decidable.
\begin{proof}
The key is to realize that \textbf{a $\mathsf{LBA}$ has a finite number of possible configurations.} A general Turing machine can access an arbitrary number of tape cells, but a LBA can only move on and modify the tape area containing the input. Specifically, to calculate the number of possible configurations:
\begin{itemize}
\item The number of possible states is $|Q|$.
\item The number of possible head locations is the length of the input; call it $n$.
\item The number of possible tape contents is $|\Gamma|^{n}$, where $\Gamma$ is the tape alphabet.
\end{itemize}
So the number of possible configurations is exactly $|Q|\cdot n\cdot |\Gamma|^{n}$. Call this number $K$.
Now what happens if we simulate the $\mathsf{LBA}$ $B$ for $K$ steps? If after $K$ steps it has halted, we will know whether it has accepted or not. If it has still not halted, then it has gone through $K+1$ configurations. But since there are only $K$ unique configurations, $B$ must have repeated a configuration somewhere, which means it must be looping.
We can therefore construct a decider $L$ for $A_{\mathsf{LBA}}$:\\
$L =$ `` On input $\left****$, where $B$ is a $\mathsf{LBA}$ and $w$ is a string:
\begin{itemize}[label=-]
\item Simulate $B$ on $w$ for $K$ steps, where $K=|Q|\cdot n\cdot |\Gamma|^{n}$, and $n$ is the length of $w$.
\item If the simulation accepts, \textit{accept}.
\item If the simulation rejects or has not halted, \textit{reject}.
\end{itemize}
\end{proof}
\section{Computation History Method}
Often, our reduction proofs in this class have a step that looks like ``Simulate $M$ on $w$.'' But what if we are working with a model of computation which can't simulate Turing machines?
\subsection{Computation Histories}
Let the \textit{computation history} of $M$ on $w$ be the sequence of configurations $C_{1}, C_{2}, \hdots, C_{k}$ that $M$ goes through when given input $w$. Note that for a given deterministic $M$ and input string $w$, there exists only one computation history of $M$ on $w$.
When we write out computation histories on a tape, we encode each configuration $C_{i}$ as a string $c_{i}$. We then join together the strings $c_{i}$, separating them by a marker symbol $\#$ (which we assume by convention is not in any of the original strings $c_{i}$). Then, our entire encoded history looks like $c_{1} \# c_{2} \# \hdots \# c_{k}$.
\subsection{The Idea}
If $M$ accepts $w$, then the computation history of $M$ on $w$ will satisfy the following three properties:
\begin{enumerate}
\item $C_{1}$ is the correct start configuration: the machine is in the start state $q_{0}$, the head is at the start of the tape, and the tape contains the input $w$.
\item $C_{k}$ is an accepting configuration: the machine is in the accept state $q_{\text{acc}}$.
\item For each $i\in[1, k-1]$, $C_i$ yields $C_{i+1}$ according to the transition function of $M$.
\end{enumerate}
The big ideas at play are that:
\begin{itemize}
\item An accepting computation history of $M$ on $w$ \textit{\textbf{exists}} if and only if $M$ accepts $w$, and
\item Checking whether a given computation history is a \textbf{\textit{accepting/rejecting computation history of $M$ on $w$}} is easier than simulating $M$ on $w$.
\end{itemize}
\subsection{When to use this method}
The computation history method is often suitable for problems which:
\begin{itemize}
\item Deal with \textit{existence}. Philosophically, this is because $M$ accepts $w$ if and only if there \textit{exists} some accepting computation history of $M$ on $w$.
\item Involve models of computation which are not as powerful as Turing machines (and thus can't simulate them). When simulating $M$ on $w$ is not possible, it's natural to ask whether one can instead check \textit{computation histories} of $M$ on $w$. I like to describe this using the \textbf{pset grader mentality:}
\quote{\textit{I might not remember how to solve this problem by myself, but I am 100\% absolutely certain that every step in this student's solution is correct (or that a certain step in this student's solution is wrong).}}
\end{itemize}
Indeed, the examples we've seen using the computation history method fall roughly under these criteria: $E_\mathsf{LBA},ALL_\mathsf{CFG},$ etc.
\subsection{\texorpdfstring{$E_{\text{LBA}}$}{E\_LBA} is Undecidable}
Let's try to use the computation history method to prove that the following language is undecidable:
\[E_{\mathsf{LBA}} = \{\left****|\text{ B is a $\mathsf{LBA}$ and $L(B)= \emptyset$}\}\]
To show undecidability, we want to reduce from $A_{\text{TM}}$. To do so, we construct a LBA which tests if a given computation history for $M$ on $w$ is accepting. If $M$ accepts $w$, then there is some accepting computation history, and the LBA will accept this string. If $M$ does not accept $w$, then there is no accepting computation history, and the language of the LBA will be empty.
To check whether a computation history $c_{1} \# c_{2} \# \hdots \# c_{k}$ is accepting, we need to check:
\begin{enumerate}
\item The start configuration is encoded correctly: $c_{1} = q_{0} w$ (start state $q_{0}$, input $w$ on tape).
\item Each transition from $c_{i}$ to $c_{i+1}$ is correct.
\item $c_{k}$ contains the accept state $q_{\text{acc}}$.
\end{enumerate}
% of the form $q_{0}w$,
For our constructed LBA to exist, we need to show that a LBA can test all these conditions, given the computation history as input. For the start configuration, we need to check that $c_{1}$ matches the finite string $q_{0}w$; as this is a finite amount of information, we can encode it into the states of the LBA. To check a transition $c_{i} \to c_{i+1}$, the LBA can sweep across the two configurations, comparing matching portions of them and checking that the transition is valid. For the last configuration, the LBA just needs to check that $q_{\text{acc}}$ is on the tape.
After arguing we can construct an LBA to check computation histories, we can write out our reduction:
\begin{proof}
Reduce from $A_{\mathsf{TM}}.$
Assume for sake of contradiction that we have a decider for $E_{\mathsf{LBA}}$; call it $D$. Then construct a decider for $A_{\mathsf{TM}}$ as follows:\\
$L=$ `` On input $\left$:
\begin{enumerate}
\item Construct a LBA, $B_{M,w}$, which tests if a given computation history for $M$ on $w$ is accepting or not.
\item Feed $\left< B_{M,w} \right>$ into $D$.
\item If $D$ accepts, then $L(B)$ is empty and there is no accepting computation history of $B$ on $w$, so we can \textit{reject}.
\item If $D$ rejects, then $L(B)$ is nonempty and there is an accepting computation history of $B$ on $w$, so we can \textit{accept}.
\end{enumerate}
\end{proof}
\subsection{\texorpdfstring{$ALL_{\text{PDA}}$}{ALL\_PDA} is Undecidable}
Let's use the computation history method to show another language is undecidable:
\[ALL_{\text{PDA}}=\{\left|\text{ $M$ is a PDA and $L(M)=\Sigma ^*$}\}\]
\begin{proof}
Reduce from $A_{\mathsf{TM}}.$
Assume for sake of contradiction that we have a decider for $ALL_{\text{PDA}}$; call it $D$. Then construct a decider for $A_{\mathsf{TM}}$ as follows:\\
$L=$ `` On input $\left$:
\begin{enumerate}
\item Construct a PDA, $P_{M,w}$, which accepts all strings that are not an accepting computation history of $M$ on $w$.
\item Feed $\left$ into $D$.
\item If $D$ accepts, that means that there's no accepting computation history of $M$ on $w$ , so we can \textit{reject}. (otherwise $\left$ would have rejected that history, and hence $D$ would have rejected as well)
\item Similarly, if $D$ rejects, \textit{accept}.''
\end{enumerate}
The overall logic in this reduction is very similar to the previous problem. The only new component is the structure of $P_{M,w}$: instead of checking for accepting computation histories, we check for rejecting ones.
When checking accepting computation histories, we need multiple conditions (start state, transitions, accept state) to all hold. However, when checking for non-acceptance, we only need one of the conditions to fail. We can then split the checking into threads, with each thread checking a single condition.
The main idea behind the construction is that the PDA can non-deterministically check for all the possible errors in the history, and accept a string if it has any error. Recall that $w$ is an accepting computation history if and only if:
\begin{enumerate}
\item $c_{1} = q_{0}w$
\item $c_{i + 1}$ follows by a single legal transition from $c_{i}$
\item $c_{k}$ has an accept state
\end{enumerate}
To check that (1) does not hold, $P_{M,w}$ can hard code the expected $c_{1}$ and accept if it does not match. Similarly for (3), it can scan the input and accept if it never sees an accept state of the Turing machine. Checking that (2) does not hold for some $i$ is a little trickier.
To check for (2), we would hope to use the stack to store $c_{i}$ and compare it with $c_{i+1}$. After all, if the computation history is legitimate, they should be equal except for at most two consecutive places (the old and new locations of the head). The only issue is that when we push $c_{i}$ into the stack it comes out reversed. To deal with this, we change the definition of the computation history so that it reverses every other configuration. In particular, instead of $c_{1} \# c_{2} \# c_{3} \# c_{4} \# \dots$, the computation history is defined as $c_{1} \# c_{2}^{R} \# c_{3} \# c_{4}^{R} \# \dots$. That way, when we push $c_{i}$ into the stack, it comes out in the same orientation as $c_{i+1}$.
To summarize, $P_{M,w}$ accepts all strings other than an accepting computation history of $M$ on $w$, where every other configuration is written in reverse. To do so, it none-deterministically pushes $c_{i}$ on the stack, and looks for an error in the transition to $c_{i+1}$ by comparing one element at a time. If any of those threads finds a discrepancy it accepts. It also has a hardcoded expectation for $c_{1}$ and it accepts if it does not match it, and it accepts if it never sees an accept state of the Turing machine.
Since the language of $P_{M,w}$ is all strings if and only if $M$ does not accept $w$, it allows us to use a decider for $ALL_{\text{PDA}}$ to construct a decider for $A_{\text{TM}}$, which proves that $ALL_{\text{PDA}}$ is not decidable.
\end{proof}
**