CS46 — Homework 6


Due Thursday 27 March at start of class
Starting files are available from my public cs46 folder 
cd ~/cs46/
cp -r examples/homework/hw06.tex homework/
git status 
git add homework/hw06.tex
git commit -m "week6 start"
git push
You may work with a partner and submit a common solution on this homework.
In lab practice
  1. Convince yourself that it is possible to design real Turing Machines in terms of states and state transitions by constructing 1-tape Turing Machines that perform the following tasks
    1. Design a TM that decides the language $L=\{ w\#w, w \in \{0,1\}^* \}$
    2. Starting with input $w \in \{0,1\}^*$, design a machine that copies $w$ and results in the string $w\#w$ at the end of the computation. Assume the TM stops when reaching a single halting state $q_{\text{halt}}$.
  2. Describe at high level a non-deterministic TM that decides the language $L=\{ ww, w \in \{0,1\}^* \}$.
  3. How might you design a deterministic TM to decide the language above? Hint: use two tapes.
  4. Sipser 3.15: Show that the set of decidable languages is closed under union, concatenation, star, complement, and intersection.
  5. Sipser 3.16: Show that the set of Turing-recognizable languages is closed under union, concatenation, star, and intersection. We will see in class that this set is not closed under complement.