EXERCISES

$3\mathrm{.}1$ This exercise concerns TM M$2,$ whose description and state diagram appear in Example $3\mathrm{.}7.$ In each of the parts, give the sequence of configurations that M$2$ enters

when started on the indicated input string.

a$.0.$

Ab$.00.$

c$.000.$

d$.000000.$

$3\mathrm{.}2$ This exercise concerns TM M$1,$ whose description and state diagram appear in Example $3\mathrm{.}9.$ In each of the parts, give the sequence of configurations that M$1$ enters

when started on the indicated input string.

A

a$.11.$

b$.1$#$1.$

c$.1$##$1.$

d$.10$#$11.$

e$.10$#$10.$

A

$3\mathrm{.}3$ Modify the proof of Theorem $3\mathrm{.}16$ to obtain Corollary $3\mathrm{.}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.$)$

$3\mathrm{.}4$ 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.