% This work is licensed under the Creative Commons Attribution 3.0 Unported License.
% To view a copy of this license, visit http://creativecommons.org/licenses/by/3.0/
% or send a letter to Creative Commons, 171 Second Street, Suite 300, San Francisco,
% California, 94105, USA.
%
% Author: Alejandro Diaz-Caro
% Date: October 2010
\documentclass[12pt,a4paper]{article}
\usepackage{amsmath,amsfonts,amssymb}
\usepackage[top=1.5cm,right=1.5cm,bottom=1.5cm,left=1.5cm]{geometry}
\usepackage{vaucanson-g}
\makeindex
\title{Exercise sheet 3: Decidability}
\author{Alejandro D\'iaz-Caro}
\date{2010}
\begin{document}
\begin{center}
\textbf{\begin{large}Exercise sheet 3: Decidability\end{large}}
\end{center}
\begin{enumerate}
\item An {\em enumerator} is a Turing Machine that outputs strings one at a
time. For instance, a TM that outputs 1, then 11, then 111, et
cetera, is said to be an {\em enumerator} for the language $11^*$.
You may assume that the TM has a state that triggers it to output, and
it has a second tape specifically to write its output down.
The language of an enumerator is the set of all strings it will output
after any finite amount of time.
Prove that if a language has an enumerator that produces the strings
in that language in lexographic order, then that language is
decidable.
\item Prove that if a language is decidable, there is an enumerator for that
language that outputs the strings in lexographic order.
\item Let $NE_{TM} = \{\langle M \rangle~|~M$ accepts a string$\}$. Prove that $NE_{TM}$ is undecidable.
\item Here is an attempt to solve the halting problem. Explain the flaw in
the reasoning, and give an example of a machine and a string that the
proposed method would fail on. (Note: there is actually a flaw here,
not merely a lack of detail. You should find something that is false
in this paragraph and explain why, or identify something implicitly
assumed and explain why that is false.)
``In order to determine if a Turing machine is going to loop, we just
have to simulate it while keeping track of every configuration it
enters. If the simulated machine ever enters the same configuration
twice, we know it will loop, and thus, we reject. To keep track of
the configurations, we use a second tape. When we enter a new
configuration, we scan this new tape to see if this new configuration
had been seen before; if so, we reject, and if not, we write this
configuration at the end of the second tape. Whenever a TM enters the
same configuration twice, it will loop, thus, when we reject, the
machine does not halt. If the Turing machine does halt it will never
enter the same configuration twice, so we will accept. Thus, this
method shows that the halting problem is decidable.''
\end{enumerate}
\end{document}