\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\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\Res{\mathrm{Res}} % \begin{document} \begin{center} \fbox{{\Large\bf Spring, 2004 \hspace*{0.4cm} CIS 511}}\\ \vspace{1cm} {\Large\bf Introduction to the Theory of Computation\\ Jean Gallier \\ \vspace{0.5cm} Homework 6}\\[10pt] April 8, 2004; Due April 22, 2004\\ \end{center} ``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 {0.5cm} ``B problems'' must be turned in. \vspace{0.25cm} \noindent {\bf Problem B1 (20 pts).} Let us consider a version of a PDA (shift-reduce PDA) in which the transition function $\delta$ is defined as follows: We can have {\it push\/} moves \[(q, YZ) \in \delta(p, a, Z),\] where $Y, Z\in \Gamma$ (where $\Gamma$ is the stack alphabet) $a\in (\Sigma\cup\{\epsilon\})$, $p, q\in K$, or {\it extended pop moves\/} \[(q, \epsilon) \in \delta(p, a, \gamma),\] $a\in (\Sigma\cup\{\epsilon\})$, $p, q\in K$, where $|\gamma| \geq 1$ ($\gamma\in\Gamma^+$). In an extended pop move, several stack symbols can be popped at once in a single move (when $|\gamma| \geq 2$). \medskip Show that every shift-reduce PDA can be converted to an equivalent standard PDA. \medskip Show that every standard PDA can be converted to an equivalent shift-reduce PDA. \medskip\noindent {\it Hint\/}. First, convert the standard PDA to an equivalent one which contains a bottom-marker during any computation until the very end, and such that $(q, \gamma) \in \delta(p, a, Z)$ implies $|\gamma| \leq 2$. Simulate a move $(q, Y) \in \delta(p, a, Z)$ by a pop during which you remember that $Z$ was on top, followed by pushing $YU$, whatever $U$ is currently on top. A move $(q, XY) \in \delta(p, a, Z)$ is simulated in a similar fashion, but you will use two push moves after the initial pop move. \vspace {0.25cm} \noindent {\bf Problem B2 (10 pts).} Prove that the function, $\mapdef{f}{\Sigma^*}{\Sigma^*}$, given by \[ f(w) = a_1^{|w|} \] is primitive recursive ($\Sigma = \{a_1, \ldots, a_N\}$). \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 (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.25cm} \noindent {\bf Problem B5 (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 B6 (20 pts).} Prove that it is undecidable whether a context-free grammar generates a regular language. \vspace{0.25cm} \noindent {\bf Problem B7 (50 pts).} Let $\s{NEXP}$ be the class of languages accepted in time bounded by $2^{p(n)}$ by a nondeterministic Turing machine, where $p(n)$ is a polynomial. Consider the problem of tiling a $2s\times s$ rectangle, described in Section 7.5 of the notes (slides on the web), but only with a single initial tile $\sigma_0$, and assume that $s$ is given in binary. \medskip (i) Prove that the above tiling problem is $\s{NEXP}$-complete. \medskip (ii) Now, consider the problem of tiling the {\it entire upper half-plane\/}, starting with a single tile $\sigma_0$ (of course, the set of tile patterns, $\s{T}$, is finite). More precisely, this problem is said to have a solution if for every $s > 1$, there a function $\sigma_s$ tiling the $2s\times s$-rectangle. \medskip Prove that this problem is undecidable. \vspace{0.5cm}\noindent {\bf TOTAL: 190 points.} \end{document} \vspace{0.25cm} \noindent {\bf Problem B6 (extra credit, 60 pts).} Let $\Delta$ be an alphabet containing at least two letters, and let $\Sigma_m = \{1, 2, \ldots, m\}$, where $m \geq 1$. Given any two sequences $U = (u_1,\ldots, u_m)$ and $V = (v_1,\ldots, v_m)$ of strings $u_i, v_i\in\Delta^*$, there are unique homomorphisms $\mapdef{f}{\Sigma^*}{\Delta^*}$ and $\mapdef{g}{\Sigma^*}{\Delta^*}$ such that $f(i) = u_i$ and $g(i) = v_i$ for all $i$, $1\leq i\leq m$. \medskip If $f(w) = g(w)$ for some string $w\in \Sigma^*$, we say that the {\it Post correspondence problem for $U$ and $V$, for short, the PCP\/}, has a solution $w$. This is equivalent to saying that there is a string $w =i_1 i_2\cdots i_n$, where $n\geq 1$ and $1\leq i_j \leq m$, such that $$u_{i_{1}} u_{i_{2}} \cdots u_{i_{n}} = v_{i_{1}} v_{i_{2}} \cdots v_{i_{n}}.$$ \medskip Prove that the Post Correspondence Problem is undecidable. \medskip\noindent {\bf Do not} use Turing machines, use RAM programs with one variable! \medskip\noindent {\it Hint\/}: Reduce the halting problem for RAM programs with one variable to the PCP (use the fact that only four kinds of instructions are needed).