[20] Define Turing machines in quadruple format with arbitrarily large tape alphabets A, and state sets Q, d(A), d(Q) < ∞. Show that each such Turing machine with state set Q and tape alphabet A can be simulated by a Turing machine with tape alphabet A

, d(A

) = 2, and state set Q such that d(A

)d(Q

) ≤ cd(A)d(Q), for some small constant

c. Determine

c. Show that the analogous simulation with d(A

) = 1 is impossible (d(Q

) = ∞).

Comments. See [C.E. Shannon, pp. 129–153 in: Automata Studies, C.E.

Shannon and J. McCarthy, eds., Princeton Univ. Press, 1956]. This is also the source for Exercise 1.12.3.