\ifx\AllTogetherMode\undefined%
\IfFileExists{../prefix.tex}%
{\input{../prefix}}%
{\input{prefix}}%
\fi
\HomeworkStart%
{12} % Homework number
{26500} % Week of semester submitted
{2.71828182845904} % Version
\SaveIndent%
\HWInstructions{%
\textbf{This homework is \scalebox{2}{not} for submission -- it is
only for exercise for the final. No solution would be
provided. %
}%
\medskip%
\hrule %
\medskip }
\noindent%
\begin{questions}[start=34]
\RestoreIndent%
\item Recall that $w^R$ denotes the reversal of string $w$; for
example, $\Sym{TURING}^R = \Sym{GNIRUT}$. Prove that the following
language is undecidable.
\[
\textsc{RevAccept}:= \Set{\seq{M}}{\text{$M$ accepts
$\seq{M}^R$}}
\]
Note that Rice’s theorem does \emph{not} apply to this language.
% ----------------------------------------------------------------------
\item Let $M$ be a Turing machine, let $w$ be an arbitrary input
string, and let $s$ be an integer. We say that \EMPH{$M$ accepts
$w$ in space $s$} if, given $w$ as input, $M$ accesses only the
first $s$ (or fewer) cells on its tape and eventually accepts.
\begin{questions}
\item Sketch a Turing machine/algorithm that correctly decides
the following language:
\[
\Set{\Seq{M,w}} {\text{$M$ accepts $w$ in space
${\abs{w}}^2$}}
\]
\item Prove that the following language is undecidable:
\[
\Set{\Seq{M}} {\text{$M$ accepts at least one string $w$
in space ${\abs{w}}^2$}}
\]
\end{questions}
% ----------------------------------------------------------------
\item Consider the language
$\textsc{SometimesHalt} = \brc{ \seq{M} \mid \text{$M$~halts on at
least one input string}}$. Note that
$\seq{M}\in \textsc{SometimesHalt}$ does not imply that $M$
\emph{accepts} any strings; it is enough that $M$ \emph{halts} on
(and possibly rejects) some string.
\begin{questions}
\item Prove that \textsc{SometimesHalt} is undecidable.
\item Sketch a Turing machine/algorithm that \emph{accepts}
\textsc{Sometimes{}Halt}.
\end{questions}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\item For each of the following languages, either prove that the
language is decidable, or prove that the language is undecidable.
\begin{questions}
\item
$L_0 = \Set{\seq{M}\strut} {\text{given any input string, $M$
eventually leaves its \State{start} state}}$
\medskip
\item $L_1 = \Set{\seq{M}\strut}{\text{$M$ decides $L_0$}}$
\item $L_2 = \Set{\seq{M}\strut}{\text{$M$ decides $L_1$}}$
\medskip
\item $L_3 = \Set{\seq{M}\strut}{\text{$M$ decides $L_2$}}$
\medskip
\item $L_4 = \Set{\seq{M}\strut}{\text{$M$ decides $L_3$}}$
\end{questions}
\end{questions}
\HomeworkEnd{}