\documentclass[12pt]{article}
\usepackage{fullpage-old} \usepackage{fancyhdr}
\usepackage{amsmath} \usepackage{amsfonts} \usepackage{amssymb}
\usepackage{graphics} \usepackage{epsfig} \usepackage{wrapfig}
\usepackage{enumitem}
\lhead{} \cfoot[]{}%{ of 1}
\pagestyle{fancy} \renewcommand{\headrulewidth}{0pt}
\fancypagestyle{plain}{ \renewcommand{\headrulewidth}{0pt} }
\parskip 1ex
\parindent 0mm
\newcommand*{\ii}[1]{\textit{#1\/}}
\def\mi{\mathit}
\def\ttt{\texttt}
\def\ss{\hspace{1pt}}
% Logical operators
\def\andl{\wedge}
\def\orl{\vee}
\def\xorl{\oplus}
\def\notl{\neg}
\def\impl{\implies}
\begin{document}
%{\flushright Name: \rule{15em}{0.25pt} \par}
\vspace{-2ex}
{\center \Large FLAC Assignment 8\par}
\vspace{2ex}
%\begin{wrapfigure}{r}{3.3in}
%\vspace{-3ex}
%\includegraphics[scale=1.2]{hw2-fig.pdf}
%\end{wrapfigure}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\paragraph{Exercise 1.} Show that the question of whether a Turing Machine halts
on a blank tape is undecidable.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\paragraph{Exercise 2.} A \emph{queue automaton} is like a pushdown automaton
except that the stack is replacd by a queue. A \textit{queue} is a tape
allowing symbols to be written only on the left-hand end and read only at the
right-hand end. Each write operation (we'll call it a \ii{push}) adds a symbol
to the left-hand end of the queue and each read operation (we'll call it a
\ii{pull}) reads and removes a symbol at the hand-hand end. As with a PDA, the
input is placed on a seperate read-only input tape, and the head on the input
tape can move only from left to right. The input tape contains a cell with a
blank symbol following the input, so that the end of the input can be detected.
A queue automaton accepts its input by entering a special accept state at any
time.
Show that the question of whether a deterministic queue automaton (DQA) halts on
a tape is undecidable. (Hint: Show that a language can be recognized by a DQA
iff the language is Turing-recognizable.)
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\paragraph{Exercise 3.}
\begin{enumerate}[label=\bf\alph*.]
\item We have defined \ii{recursively enumerable (r.e.)} languages as those
that can be recognized by a Turing Machine. Using this definition, show that
every recursively enumerable language $B$ has a computable function $f$ that enumerates $B$, i.e., that
$$B = \{f(n) \;|\; n \in \mathbb{N} \} = \{f(0), f(1), \ldots\}$$
Note that a similar result in proved in your textbook. Your proof may closely
follow the book's proof, but do not simply copy
the proof from the book. Rather, after you absorb the main idea from the book,
close the book and write out the proof by yourself.
\item Show that if a language $B$ is recursively enumerated by a \emph{strictly increasing}
computable function $f$ (so $n < m \,\impl\, f(n) < f(m)$), then $B$ is recursive (decidable).
\item Use these facts to prove that every infinite r.e.~language has an infinite recursive subset.
\end{enumerate}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\paragraph{Exercise 4.}
\begin{enumerate}[label=\bf\alph*.]
\item Give a Turing Machine that computes the function $f(n) = 2^n$ in unary
notation.
(Give a low-level implementation description and indicate the number of states
required. You need not explicitly draw a state diagram or give a formal
transition table.) You may refer to the \textsf{Double} function from the previous
homework in your description. (I.e., you don't need to describe how to implement
\textsf{Double} again.)
\item Referring to your solution in Part~(a) above, give a low-level
implementation description of a Turing Machine that computes
$f(n) = %2 \uparrow \uparrow n =
\underbrace{2^{2^{{}^{.\,^{.\,^{.\,^{2^n}}}}}}}_{\mbox{$n$ copies of 2}}
$%, where the double-arrow notation is Knuth's up-arrow notation (see Wikipedia for more information)
. Indicate the number of states.
\item What does your answer in the above part tell you about the Busy Beaver
function?
\end{enumerate}
\end{document}