Question 3 (12 Marks)
Describe two different Turing machines, M and N, that, when started on any input, M outputs <N> and N outputs <M>.
Solution:
To solve this problem, we have to be care ful about circular definitions , that is, defining M in terms of N,and N in terms of M. Remember that q(w) is a T.M. that prints w on its tape, and halts.
M= ” On input w:
(a) Ignore input.
(b)Obtain (M) by the recursion theorem.
(c)Compute q((M)),and write it to the tape.
(d)Halt ”
We let N = q((M)). When M runs, it writes N = (q((M))) in its tape, and when N runs, it writes (M) in its tape.