Turing Machine running itself?

2.4k Views Asked by At

I am reading a proof that shows that the language

$A_{TM} = \{\langle M, w\rangle \mid M$ is a $TM$ and $M$ accepts $w\}$ is undecidable.

The proof proceeds by supposing there is a decider for the language $H,$ and a new TM $D$ that calls $H$ as a subroutine. $D$ runs by the following: On input $\langle M\rangle$, where $M$ is a TM, run $H$ on $\langle M, \langle M\rangle\rangle$. Output the opposite of what H outputs... I am confused by what $\langle M, \langle M\rangle\rangle$ means. Can somebody explain what it means for a machine to run on its own description?

1

There are 1 best solutions below

0
On

From your question I assume that you use a definition of Turing machines which are defined on strings as input. If $M$ is the description of a Turing machine, then $\langle M \rangle$ would be the description as a string, so you can actually use it as input. The technique of running a Turing machine with its own code as input is widely known as "diagonalization", a proof technique widely used in computability theory.

By clever coding you can build a one-one correspondence between finite strings and descriptions of Turing machine. I am sure that this is explained in the text you are reading, for instance when Universal Turing machines are introduced.

In the notation widely accepted in the computability theoretic community where $\phi_x$ is the Turing machine with code $x$ and assuming that your machine $D$ has code $d$, it would read as $$\phi_d(x)=\begin{cases} 1 & \phi_x(x)=0\\ 0& \phi_x(x)=1 \end{cases}$$