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

Convince yourself that it is possible to design real Turing Machines in terms of states and state transitions by constructing 1tape Turing Machines that perform the following tasks
 Design a TM that decides the language $L=\{ w\#w, w \in \{0,1\}^* \}$
 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}}$.
 Describe at high level a nondeterministic TM that decides the language $L=\{ ww, w \in \{0,1\}^* \}$.
 How might you design a deterministic TM to decide the language above? Hint: use two tapes.
 Sipser 3.15: Show that the set of decidable languages is closed under union, concatenation, star, complement, and intersection.
 Sipser 3.16: Show that the set of Turingrecognizable languages is closed under union, concatenation, star, and intersection. We will see in class that this set is not closed under complement.