Using the algorithm in Theorem 53 (loosely), convert the 3TM in Problem 11 into a simple TM.
Theorem 53
(i) Given any TM and any k, there is a kTM that acts on all inputs exactly as the TM does (that means either loops, crashes, or leaves a corresponding output).
(ii) Given any kTM for any k, there is a TM that acts on all inputs exactly as the kTM does (that means loops, crashes, or leaves a corresponding output).
In other words, as acceptor or transducer:
TM = TM
Problem 11
(i) Write a 3TM to do binary addition on two n-bit numbers.
(ii) Describe a TM that multiplies two 2-bit binary numbers, called an MTM.