\documentclass[12pt]{article}
\usepackage{amsfonts}
%\documentstyle[12pt,amsfonts]{article}
%\documentstyle{article}

\setlength{\topmargin}{-.5in}
\setlength{\oddsidemargin}{0 in}
\setlength{\evensidemargin}{0 in}
\setlength{\textwidth}{6.5truein}
\setlength{\textheight}{8.5truein}
%\input ../basicmath/basicmathmac.tex
%
%\input ../adgeomcs/lamacb.tex
\input ../adgeomcs/mac.tex
\input ../adgeomcs/mathmac.tex

\def\Hom#1#2#3{\mathrm{Hom}_{#1}(#2, #3)}
\def\fseq#1#2{(#1_{#2})_{#2\geq 1}}
\def\fsseq#1#2#3{(#1_{#3(#2)})_{#2\geq 1}}
\def\qleq{\sqsubseteq}
\def\buildrell#1\over#2{\mathrel{\mathop{\null#1}\limits_{#2}}}
\def\rmder#1{{\ \buildrell  \Longrightarrow \over{rm}}^{#1}\ }
\def\lmder#1{\buildrel #1\over{\buildrell  \Longrightarrow \over{lm}}}
\def\der#1{\buildrel #1\over\Longrightarrow}
\def\Res{\mathrm{Res}}

%
\begin{document}
\begin{center}
\fbox{{\Large\bf Spring, 2003 \hspace*{0.4cm} CIS 511}}\\
\vspace{1cm}
{\Large\bf Introduction to the Theory of Computation\\
\vspace{0.5cm}
Homework 6}\\[10pt]
April 17, 2003; Due April 28\\
\end{center}

%\vspace {0.5cm}
%``B problems'' must be turned in.


``A problems'' are for practice only, and should not
be turned in.

\vspace {0.25cm}
\noindent
{\bf Problem A1.} 
Prove that every  context-free language is a recursive set.

\vspace {0.25cm}
\noindent
{\bf Problem A2.} 
Consider the definition of the Kleene $T$-predicate given
in the notes in Definition 5.4.1.

\medskip
(i)
Verify that $T(x, y, z)$ holds iff $x$ codes a RAM
program, $y$ is an input, and $z$ codes a halting computation
of $P_x$ on input $y$.

\medskip
(ii)
Verify that the Kleene normal form holds:
$$\varphi_{x}(y) = \Res[\min z (T(x, y, z))].$$

\vspace {1cm}
``B problems'' must be turned in.

\vspace{0.25cm}\noindent
{\bf Problem B1 (30 pts).} 
Given $\Sigma = \{a\}$,
give a Turing machine accepting 
$$L = \{a^{2^{n}}\ |\ n\geq 1\}.$$


\vspace {0.25cm}
\noindent
{\bf Problem B2 (30 pts).} 
{\it Ackermann's function\/} $A$ is defined recursively as follows:
\[\eqaligneno{
A(0,\, y) &= y + 1,\cr
A(x + 1,\, 0) &= A(x,\, 1),\cr
A(x + 1,\, y + 1) &= A(x,\, A(x + 1, y)).\cr
}\]
Prove that
\[\eqaligneno{
A(0,\, x) &= x + 1,\cr
A(1,\, x) &= x + 2,\cr
A(2,\, x) &= 2x + 3,\cr
A(3,\, x) &= 2^{x + 3} - 3,\cr
}\]
and
\[A(4, x) = \supexpo{2}{16}{x}\> - 3,\]
with $A(4, 0) = 16 - 3 = 13$.
Equivalently (and perhaps less confusing)
\[A(4, x) = \supexpo{2}{2}{x+3}\> - 3.\]

\vspace{0.5cm}
\noindent
{\bf Problem B3 (20 pts).} 
Prove that the following properties of partial recursive functions
are undecidable.

\medskip
(a) A partial recursive function is a constant function.

\medskip
(b)
Two partial recursive functions $\varphi_x$ and $\varphi_y$
are identical.

\medskip
(c)
A partial recursive function $\varphi_x$ is equal to a given partial
recursive function $\varphi_a$.

\medskip
(d)
A partial recursive function diverges for all input.

\vspace{0.25cm}
\noindent
{\bf Problem B4 (40 pts).} 
Prove that a RAM program with $p\geq 2$ registers
can be simulated by a
RAM program with a single register, by encoding
the contents $r_1, \ldots, r_p$ of the $p$ registers
as the string
$$r_1\# r_2\# \cdots \# r_p,$$ 
using a new marker \#.

\medskip\noindent
{\it Hint\/}: Begin by simulating a RAM program with
two registers using a single register.
Another (painful) solution is to simulate a Turing machine
using a RAM with a single variable. In this case, the variable will
represent  the tape  $uav$ as $av\#u$. Some care must  be exercised
at both ends of the tape. Then, go from RAM to TM to RAM with a
single register!

\medskip
Conclude that the halting problem for RAM programs
with one register is undecidable.

\vspace{0.25cm}
\noindent
{\bf Problem B5 (50 pts).}
A {\it linear context-free grammar\/} is a context-free
grammar whose productions are of the form
either
\begin{eqnarray*}
A & \longrightarrow & u B v,\quad\hbox{or}\\
A & \longrightarrow & u,
\end{eqnarray*}
where $A, B$ are nonterminals and $u, v\in \Sigma^*$.
A language is {\it linear context-free\/} iff it is generated
by some linear context-free grammar.

\medskip
(a) 
Prove that every regular language is linear context-free.
Prove that if $L$ is a linear context-free language, then
for every $a\in \Sigma$, the language
$L/a = \{w\in \Sigma^* \mid wa \in L\}$ is also linear
context-free.

\hint
Construct a grammar using some new nonterminals,
$[A/a]$, and new productions
\[
[A/a] \longrightarrow \alpha,\quad\hbox{if}\quad
A \longrightarrow \alpha a \in P
\quad\hbox{or}\quad
A \longrightarrow \alpha a B\in P
\quad\hbox{with}\quad
B \der{+} \epsilon
\]
and
\[
[A/a] \longrightarrow u [B/a],\quad\hbox{if}\quad
A \longrightarrow u B\in P,
\]


\medskip
(b)
Prove that it is undecidable whether a context-free
language, $L$, is linear context-free.



\vspace{0.25cm}\noindent
{\bf TOTAL: 170  points.}

\end{document}