- A Turing machine with left-reset is similar to an ordinary Turing machine but the transition function has the form
$δ : Q × Γ → Q × Γ × \{ R, RESET \}$ The semantics of the
$RESET$ move is that the Turing machine will go all the back to the left-most side of the tape, instead of just moving a step left. Prove that Turing machines with left reset are equivalent to ordinary Turing machines. To do this you’ll need to- show that you can turn a Turing machine with left reset into an ordinary Turing machine (the hard part)
- show that you can turn an ordinary Turing machine into a Turing machine with left reset (the easy part)
The easiest way to do this is to simulate one type of movement with the other.
- Show, by construction, that the Turing-decidable languages are closed under
- union
- intersection
- complement
3. Give an informal description of the following languages
$\{ w | w \text{ contains twice as many 0s as 1s} \}$ $\{ w | w \text{ has matching parentheses and a length that’s a power of 2}\}$
- Show, by construction, that the Turing recognizable languages are closed under
- Kleene star
- concatenation
- reversal
Are the recognizable languages closed under complement? If not, can you give a counter-example?