CS46 — Homework 7


Due Tuesday 8 April at start of class
Starting files are available from my public cs46 folder 
cd ~/cs46/
cp -r examples/homework/hw07.tex homework/
git status 
git add homework/hw07.tex
git commit -m "week7 start"
git push
You may work with a partner and submit a common solution on this homework.
In lab practice
  1. Consider the following "reduction" from $A_{TM}$ to $E_{TM}$. Construct $f(\langle M,w \rangle)=\langle M' \rangle$ as follows: $M'$: on input $x$
    erase $x$ and write $w$
    simulate $M$ on $w$
    if $M$ accepts $w$, reject
    if you get here, accept

    Is $f$ computable? Is it true that $\langle M,w \rangle \in A_{TM} \iff \langle M' \rangle \in E_{TM}$?

  2. We know from class that $E_{TM}=\{ \langle M \rangle | M$ is a TM and $L(M) = \emptyset \}$ is undecidable.
    1. Show that $\overline{E_{TM}}$ is Turing-Recognizable
    2. Is $E_{TM}$ Turing-Recognizable? Why or why not?
  3. A linear bounded automaton is a special TM whose read write head is not allowed to read past the portion of the tape containing the input. In essence, the tape length is fixed at a finite $n= |w|$ for any input $w$. Define $A_{LBA} = \{ \langle M, w \rangle | M$ is a deterministic 1-tape LBA and $M$ accepts $w \}$.
    1. What is the maximum number of configurations of a deterministic 1-tape LBA with $|Q|$ states and $|\Gamma|$ tape symbols, given input $w$, $|w|=n$?
    2. Show that $A_{LBA}$ is decidable. In addition to this proof, the book also defines $E_{LBA}= \{ \langle M \rangle | M$ is an LBA and $L(M)=\emptyset \}$ and shows $E_{LBA}$ is undecidable.
  4. Rice's Theorem is stated as follows: Let $P$ be any non-trivial property of the language of a Turing machine, e.g., $L(M)$ contains $w$. The problem of determining if a given TM $M$ satisfies property $P$ is undecidable. $P$ is non-trivial if $P$ contains some, but not all Turing Machine descriptions. Furthermore $P$ is the property of the language of $M$, not necessarily $M$ itself. Thus if $L(M_1)=L(M_2)$ for some $M_1 \neq M_2$, then $\langle M_1 \rangle \in P $ iff $\langle M_2 \rangle \in P$. Prove Rice's theorem by assuming for the sake of contradiction that $R_P$ decides some non-trivial property $P$. Use $R_P$ to decide $A_{TM}$ a contradiction. Because $P$ is known and non-trivial, you may assume that there are two machines $T_1,T_2$ such that $\langle T_1 \rangle \in P, L(T_2) = \emptyset, \langle T_2 \rangle \not \in P$. Use $R_P, T_1$ and $T_2$ to build $S$ that decides $A_{TM}$.