\documentstyle[11pt]{article}
% frob with the margins
\addtolength{\topmargin}{-1in}
\addtolength{\footskip}{-1in}
\addtolength{\textheight}{2in}
\addtolength{\oddsidemargin}{-.5in}
\addtolength{\evensidemargin}{-.5in}
\addtolength{\textwidth}{1in}
% no page numbers
\pagestyle{empty}
% counter for page numbers
\newcounter{pg}
\setcounter{pg}{2}

% DEFINE THE PROBLEM SET NUMBER
\def\psnum{7}

% DEFINE THE DUE DATE
\def\due{\today}

% title command
\newcommand{\mytitle}{{\large\noindent 6.045/18.400 Automata,
Computability, and Complexity \hfill{} Juliet Bourne \\
Problem Set \psnum \hfill{} \due \\}
\vspace{-.6in}
\begin{center} \rule{6in}{.25mm} \end{center}}
% newpage setup command 
\newcommand{\mypage}[1]{\newpage{\large\noindent 6.045/18.400 Automata,
Computability, and Complexity \hfill{} Juliet Bourne \\
Problem Set \psnum \hfill{} \due \\}
\vspace{-.6in}
\begin{center} \rule{6in}{.25mm} \end{center}}
%\newcommand{\mynewpage}{\newpage\noindent
%{\large 6.045/18.400 \hfill{} Juliet Bourne \\
%Problem Set \psnum \hfill{} {\bf Page \thepg} \\}
%\vspace{-.6in}
%\begin{center}
%\rule{6in}{.25mm}
%\end{center}
%\addtocounter{pg}{1}}
% problem command
\newcommand{\prob}[1]{\noindent{\fbox{\large\bf Problem #1}}\vspace{.25in}}
% subproblem command
\newcommand{\subprob}[1]{\vspace{.15in} \noindent{\large\bf #1.}}
% equations commands
\newcommand{\beq}{\vspace*{-.3in}\begin{eqnarray*}}
\newcommand{\eeq}{\end{eqnarray*}}

\begin{document}

\mytitle

\prob{1: Reducibility}

\subprob{a} If $A \leq_m B$ then $\overline{A} \leq_m \overline{B}$.

\vspace*{.15in}
If $A \leq_m B$ then $\exists f$ such that $\forall w \in \Sigma^* w \in
A$ iff $f(w) \in B$. By definition of $f$, $w \not\in A$ iff $f(w) \not\in
B$. Thus $\exists f$ such that $\forall w \in \Sigma^* w \in
\overline{A}$ iff $f(w) \in \overline{B} \Rightarrow \overline{A} \leq_m
\overline{B}$ by definition.

\subprob{b} If $A$ is r.e. and $A \leq_m \overline{A}$ then $A$ is
recursive.

\vspace*{.15in}
If $A$ is r.e. and $A \leq_m \overline{A}$ then $\overline{A}$ is also
r.e. since an r.e. language is reducible to it. Therefore, since both
$A$ and $\overline{A}$ are r.e. ({\em i.e.} $A$ is r.e. and co-r.e.),
$A$ is recursive (by Theorem 6.2.1).

\subprob{c} If $A$ is recursive and $B$ is any language except
$\Sigma^*$ and $\phi$, then $A \leq_m B$.

\vspace*{.15in}
Since $A$ is recursive and $B$ is not infinite or empty, it is possible
to find a function $f$ such that $\forall w \in \Sigma^* w \in A$ iff
$f(w) \in B$. $w \in A$ is decidable since $A$ is recursive. $f$
translates points in $A$ to points in $B$ and points not in $A$ to
points not in $B$. Therefore, $A \leq_m B$.

\subprob{d} Show that $\overline{K_{TM}}$ is complete for co-r.e.

\vspace*{.15in}
By definition, $\overline{K_{TM}}$ is complete for co-r.e. iff 
\begin{enumerate}
\item  $\overline{K_{TM}}$ is co-r.e.
\item $\forall A \in$ co-r.e., $A$ is reducible to  $\overline{K_{TM}}$.
\end{enumerate}

Proof:
\begin{enumerate}
\item  $\overline{\overline{K_{TM}}} = K_{TM}$. Therefore, $\overline{K_{TM}}$ 
is co-r.e. since $K_{TM}$ (and thus $\overline{\overline{K_{TM}}}$) is r.e. 
\item $A \in$ co-r.e. $\Rightarrow \exists$ TM $M$ that accepts
$\overline{A}$. $f(x) = \langle M,x\rangle$ which is computable. $x \in
A$ iff $M$ halts and rejects $x$ iff $\langle M,x\rangle \in
\overline{K_{TM}}$.
\end{enumerate}

\mypage

\prob{2: Language Classification, Part A}

$L_a = \{\langle M\rangle : M$ on blank tape {\em eventually} writes a
non-blank symbol$\}$ is recursive. 

\vspace*{.15in}
Since $M$ has a finite number of states (by definition of being a Turing
Machine), it is possible for another TM $M'$ (which will decide $L_a$)
to simulate $M$ given $\langle M\rangle$, keep track of which states
have already been visited and observe whether any state visited writes
a non-blank symbol. If $M$ writes a non-blank symbol in any state
visited, then $M'$ accepts $\langle M\rangle$ and halts. If the
simulation of $M$ visits an already-visited state (and no non-blank
symbol has been written) then $M'$ rejects $\langle M\rangle$ and halts,
since $M$ is in a loop.

\mypage

\prob{2: Language Classification, Part B}

$L_b = \{\langle M \rangle : M$ accepts an even-length string$\}$ is
r.e. but not recursive.

\vspace*{.15in}
$L_b$ is r.e. since given $\langle M\rangle$ some TM $M'$ can simulate
$M$ $i$-steps at a time on all even-length strings $w_1, ... , w_i$ for
$i = 1, 2, 3...$.  If $M$ accepts any $w_j$, then $M'$ accepts $\langle
M\rangle$. 

However, $L_b$ is not recursive since the above process could go on
forever, never halting. If $L_b$ were recursive, then $\overline{L_b}$
would be r.e., which it isn't. Trying to use the same method used to
show that $L_b$ is r.e. won't work since for $\overline{L_b}$, $M'$
would halt and {\em reject} if $\overline{M}$ (which does not accept an
even-length string) accepted an even-length string. However, $M'$ would
not halt and {\em accept} since $M'$ will continue to enumerate
even-length strings {\em ad infinitum}. Thus, since $L_b$ is not
co-r.e., it cannot be recursive.

\mypage

\prob{2: Language Classification, Part C}

$L_c = \{\langle M\rangle : L(M)$ is regular$\}$ is r.e. but not recursive.

\vspace*{.15in}
Proof is by Rice's Theorem: The property of being regular is not trivial
since it isn't empty nor is it the property of being r.e. Thus, by
Rice's Theorem, $C_R = \{\langle M\rangle | L(M)$ has property $R\}$ is
undecidable for any non-trivial property $R$, $L_c$ is undecidable (not
recursive).

$L_c$ is r.e. since it is possible to enumerate all regular expressions
and, using the conversion procedure of a regular expression to a FA,
generate an encoding for each FA corresponding to a regular expression.

\mypage

\prob{2: Language Classification, Part D}

$L_d = \{\langle M,w\rangle : \exists k$ such that $M$ on input $w$ uses
less than $k$ tape squares$\}$ is r.e. but not recursive.

\vspace*{.15in}
Proof is by reduction to $K_{TM}$: Suppose $L_d$ is recursive. So
$\exists$ TM $R_d$ which decides $L_d$. Construct $S$ that decided
$K_{TM}$. 

S: ``On input $\langle M,x\rangle$, give it to $R_d$. If $R_d$ accepts
$\langle M,x\rangle$ then accept and halt. If $R_d$ rejects $\langle
M,x\rangle$ then reject and halt.''

So, $S$ accepts $\langle M,x\rangle$ iff $R_d$ accepts $\langle
M,x\rangle$ iff $\exists k$ such that $M$ on input $x$ uses less than
$k$ tape squares. But $K_{TM}$ is not recursive and $S$ cannot exist.
Therefore, $R_b$ cannot exist and thus $L_d$ is not recursive.

\mypage

\prob{3: Enumeration of recursive languages}

Algorithm for a TM that decides an infinite language $L$:

\begin{enumerate}
\item Given some string $w$ with length $n$, reject $w$ if it is not of
the proper form.
\item Enumerate each string of $L$ in increasing order until a string
with length greater than $n$ is found. For each string enumerated,
compare it with $w$. If $w$ matches an enumerated string, then accept
$w$. Otherwise reject $w$.
\end{enumerate}

If the string in $L$ cannot be enumerated in increasing order, then
there is no algorithm which can decide $L$.


\end{document}
