1. Design a 1-tape DTM that, on input 0^m 1 0^n halts (and accepts) with 0^{f(m,n)} on the tape. f(m,n) = m-n if m >= n, = 0 otherwise.
Trace the IDs on inputs 0000100, 00100 and 001000.

2. Suppose a k-tape DTM requires n steps on some input. Analyse the number of steps needed by the equivalent 1-tape DTM.

(See Ch-7 of Sipser: Complexity relationships among models)

3. Extend the PDA to use k-stacks in the usual manner. Explain how to formally specify such a k-stack PDA. Then show how to simulate any TM using a 2-stack PDA (you may find it useful to assume that every input always ends with a special # symbol, and # appears nowhere else in any input).