# Michael Sipser Edition 3 Exercise 3 Question 1 (Page No. 187)

34 views

This exercise concerns $TM\: M_{2}$, whose description and state diagram appear in Example $3.7$. In each of the parts, give the sequence of configurations that $M_{2}$ enters when started on the indicated input string.

1. $0$
2. $00$
3. $000$
4. $000000$

## Related questions

1
100 views
Give a formal definition of an enumerator. Consider it to be a type of two-tape Turing machine that uses its second tape as the printer. Include a definition of the enumerated language.
Modify the proof of Theorem $3.16$ to obtain Corollary $3.19$, showing that a language is decidable iff some nondeterministic Turing machine decides it. (You may assume the following theorem about trees. If every node in a tree has finitely many children and every branch of the tree has finitely many nodes, the tree itself has finitely many nodes.)
This exercise concerns $TM\: M_{1}$, whose description and state diagram appear in Example $3.9$. In each of the parts, give the sequence of configurations that $M_{1}$ enters when started on the indicated input string. $11$ $1\#1$ $1\#\#1$ $10\#11$ $10\#10$