# 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\)