\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{8}

% DEFINE THE DUE DATE
\def\due{April 19, 1991}

% 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: Rice's Theorem}

\subprob{a} $K_{B5} = \{ \langle M\rangle : M$ is a TM that halts on
blank tape with its head o the 5th tape square.$\}$

Rice's theorem cannot be used since $K_{B5}$ involves the working of the
machine $M$ itself, and not a property of the language $L(M)$.

It has already been shown that $K_{BT}$ is undecidable. Therefore,
$K_{B5}$ must also be undecidable since $K_{BT}$ must be decided before
$K_{B5}$ can be decided.

\subprob{b} $L_{nr} = \{\langle M \rangle : L(M)$ is not recursive.$\}$

Rice's theorem can be used since $L_{nr}$ involves a property of the
language $L(M)$. $R = $non-recursive.

Show that $R$ is not a trivial property by showing an r.e. language not in
$R$ and an r.e. language in $R$.
\begin{itemize}
\item $K_{TM}$ is r.e. and $K_{TM} \in R$.
\item $L = \{a^nb^n | n \geq 0\}$ is r.e. but $L \not\in R$ since it is
recursive. 
\end{itemize}

Therefore by Rice's theorem, $L_{nr}$ is undecidable.

\subprob{c} $L_n = \{\langle M \rangle : L(M)$ has exactly $n$
elements.$\}$

Rice's theorem can be used since $L_n$ involves a property of the
language $L(M)$. $R = $has exactly $n$ elements for some $n$.

Show that $R$ is a non-trivial property by showing an r.e. language in
$R$ and one that is not:
\begin{itemize}
\item $L = \{1,2,...,n\}$ is r.e. and $L \in R$ for all $n$ since it has
$n$ elements.
\item $L = \phi$ is r.e. but $L \not\in R$ for all $n > 0$.
\end{itemize}

Therefore by Rice's theorem, $L_n$ is undecidable.

\subprob{d} $L_{state} = \{ \langle M \rangle : L(M)$ is the number of
states of $M.\}$

Rice's theorem can be used since $L_{state}$ involves a property of the
language $L(M)$. Even though that property involves the machine $M$, it
still is a property of the language $L(M)$. $R = $ is number of states
of $M$.

Show that $R$ is non-trivial by showing an r.e. language in $R$ and one
that is not in $R$.
\begin{itemize}
\item $L = \{1\}$ where $M$ has one state is r.e. and $L \in R$.
\item $L = \{2\}$ where $M$ has one state is r.e. but $L \not\in R$.
\end{itemize}

\mypage

\prob{2: Post's Correspondence Problem}

\subprob{a} PCP is decidable over a unary alphabet.

If there's only one alphabetic symbol, then PCP is simply deciding
whether the sum of the lengths of the $u_i$'s, the tops of the pairs in
$P$, is equal to the sum of the lengths of the $v_i$'s, the bottoms of
the pairs in $P$. If the sums are equal then there is a match no matter
what order the pairs are put in. If the lengths are not the same, then
there can never be a match. Deciding whether the length of one string is
equal to the length of other is recursive. Therefore PCP over a unary
alphabet is decidable.

\subprob{b} $EQ_{cfg} = \{ \langle G_1, G_2 \rangle: G_1, G_2$ are CFGs
and $L(G_1) = L(G_2)\}$.

$EQ_{cfg}$ in undecidable, proof by reduction of PCP to $EQ_{cfg}$.

Assume that there is some $R$ which decides $EQ_{cfg}$. Construct $S$ that
decides PCP. 

$S$: `` On input $\langle P\rangle$, construct $G_1 = \{ S \rightarrow
u_iSv_i^R | \varepsilon$ where $(u_1 v_1) \in P\}$ and $G_2 = \{ S
\rightarrow aSb | \varepsilon$ where $a \neq b$ and $a,b \in \Sigma^* -
\varepsilon\}$. Run $R(\langle G_1, G_2 \rangle)$. If $R$ accepts, then
reject. If $R$ rejects, then accept.''

If $P$ contains a match, then $L(G_1)$ will contain a palindrome.
$L(G_2)$ contains no palindromes, by definition. Therefore, if $P$
contains a match, then $L(G_1) \neq L(G_2)$.

So, $L(S) = $ PCP. Therefore, since PCP is undecidable, $R$ cannot exist
and $EQ_{cfg}$ is not decidable.

\mypage

\prob{3: Speedup Theorem}

\subprob{a} Since strings in both $L_1$ and $L_2$ can be decided in
$T(x)$ time, $L_1 \cup L_2$ can be decided in $2 T(x) = T(x)$ time.
(First check to see if a string is in $L_1$ and then, if not, see if
it's in $L_2$.)

\subprob{b} Since all the string in $L_1 \cap L_2$ are in both $L_1$ and
$L_2$, $L_1 \cap L_2$ can be decided in $2 T(x) = T(x)$ time. (Check to
see if a string is in both $L_1$ and $L_2$.)

\subprob{c} In order to decide $L_1 \circ L_2$, a TMN must look at all
subsctrings $a, b$ of some string $x$ such that $x = ab$ and decide if
$a \in L_1$ and if $b \in L_2$. The longer the string, the more
substrings there are to look at. The number of pairs of substrings that
have to be examined is proportionate to $|x|$, and the examination of
each pair takes $2 T(x) = T(x)$ time. Therefore deciding $L_1 \circ L_2$
takes $ |x| T(x)$ time.

\mypage

\prob{4: Ordering by asymptotic growth rates}

Definition 6.2.1: $f = O(g)$ if $f(n) \leq c \cdot g(n)$ for all $n \geq n_0$.

\beq
1 = O(\log \log n) & \,\,\,\,\,\,\,\, & c = 100 \,\,\, n_0 = 10 \\
\log \log n = O(\log n) & \,\,\,\,\,\,\,\, & c = 1 \,\,\, n_0 = 2 \\
\log n = O(\log^2 n) & \,\,\,\,\,\,\,\, & c = 1 \,\,\, n_0 = 10 \\
\log^2 n = O(n) & \,\,\,\,\,\,\,\, & c = 1 \,\,\, n_0 = 1 \\
n = O(n \log n) & \,\,\,\,\,\,\,\, & c = 1 \,\,\, n_0 = 10 \\
n \log n  = O(n^2) & \,\,\,\,\,\,\,\, & c = 1 \,\,\, n_0 = 1 \\
n^2 = O(n^3) & \,\,\,\,\,\,\,\, & c = 1 \,\,\, n_0 = 1 \\
n^3 = O(\left(\frac{3}{2}\right)^n) & \,\,\,\,\,\,\,\, & c = 1 \,\,\, n_0 =24\\
\left(\frac{3}{2}\right)^n = O(2^n) & \,\,\,\,\,\,\,\, & c = 1 \,\,\, n_0 = 1\\
2^n = O(e^n) & \,\,\,\,\,\,\,\, & c = 1 \,\,\, n_0 = 1 \\ e^n = O(n2^n)
& \,\,\,\,\,\,\,\, & c = 1 \,\,\, n_0 = 2 \\ n2^n = O(n!) &
\,\,\,\,\,\,\,\, & c = 1 \,\,\, n_0 = 6 \\ n! = O((n+1)!) &
\,\,\,\,\,\,\,\, & c = 1 \,\,\, n_0 = 1 \\ (n+1)! = O(2^{2^n}) &
\,\,\,\,\,\,\,\, & c = 1 \,\,\, n_0 = 1 \\ 2^{2^n} = O(2^{2^{n+1}}) &
\,\,\,\,\,\,\,\, & c = 1 \,\,\, n_0 = 1
\eeq

\mypage

\prob{5: PALINDROME $\in \cal P$}

\begin{enumerate}
\item Move right and read symbol. Remember it and mark it. $\Rightarrow O(1)$
\item Scan left for end-of-tape or marked symbol. $\Rightarrow O(n)$
\item Move right. Read and compare symbol with remembered symbol. If
symbol is marked, then done; accept. If it matches, then mark it and
scan to the right for marked symbol and then goto 1. Otherwise reject.
$\Rightarrow O(1) + O(n)$
\end{enumerate}

The cost of an iteration of this algorithm is $O(1) + O(n) + O(1) + O(n)
= O(n)$. The number of iterations is $O(n/2) = O(n)$ for a string with
length $n$. Thus, the time taken in deciding is $O(n) \cdot O(n) =
O(n^2)$. 

\end{document}


