Problem 1: Multi-(tape) Kill
Summarize each direction of the proof of equivalence of ordinary TMs and multi-tape Turing machines in a sentence a piece.
Multi-tape Turing machines have a finite, fixed number of tapes at construction time. Suppose we tried extending the model so that the machine had an infinite number of tapes at construction time. Describe the fundamental difficulties we would encounter in trying to construct and execute such a model.
In contrast, imagine extending the model so that the multi-tape model can have a dynamic, unbounded number of tapes. The model would need an operation to spawn a new tape and the transition function would need to be modified to operate over a list of tapes. In contrast to the infinite tape model, does this variant seem equivalent to ordinary TMs? Why?
Problem 2: The Matrix
Summarize each direction of the proof of equivalence of ordinary TMs and non-deterministic TMs in a sentence a piece.
When converting NFAs to DFAs, we induced a state explosion, drastically increasing the space complexity of the automata. Where does this space hit occur in the NTM-to-TM transformation?
Review the proof of the NTM-to-TM transformation in the book (theorem 3.16).
- What is the purpose of the “address” in the construction?
- What does the TM do if a string is not accepted by the original NTM? How do we fix this problem?
Problem 3: Blah Blah Blah
Summarize each direction of the proof of equivalence of ordinary TMs and enumerators in a sentence a piece.
Give a formal description of what an enumerator is. Include a rigorous description of its components, its behavior, and the inclusion condition for its language, i.e., the condition under which \(w \in L(E)\) for some enumerator \(E\)