Question

Describe two different Turing machines, M and N, where M outputs <N> and N outputs when started on any input.

Short answer

Answer:

Two Turing Machine M and N are constructed.

Step-by-step solution

Turing Machine

A Turing Machine is computational model concept that runs on the unrestricted grammar of Type-zero. It accepts recursive enumerable language. It comprises of an infinite tape length where read and write operation can be perform accordingly.

Constructing Turing Machine

Construct a Turing Machine as following:

$M=oninput<W>$

Obtain <M> using recursion theorem

Compute q<M>and the output will be write on the tape.

Make Turing Machine Halt

So we designed the Turing Machine M as above step.

Now let us assume N = q<M>

We construct Turing Machine N as follows:

N=on input<W>

Obtain <N> using recursion theorem

Compute <q<M>>= <N>

Now N will write <M> to the tape

The last line shows that construction of M and N are correct in such a way that, ‘TM M will produce <N> and TM N produce <M> for any input’.