Does this turing machine exist?

66 Views Asked by At

I must test whether or not this Turing Machine exists $M(n)=0$ If $n$ is the Gödel number of a Turing Machine that stops with the empty tape $M(n)=1$ in other case.

1

There are 1 best solutions below

0
On

"Proof" Reasoning for the absurd, suppose that $ M (n) $ exists, let's define $ Q (n) = 1 $ if and only if $ M (n) = 1 $ and $ Q (n) = loop $ if and only if $ n = \emptyset $. Note that $ Q $ has a Gödel number which we will denote for $ z $

If $ Q (z) = 1 $ then $ M (z) = 1 $, therefore $ z $ is the Gödel number of a Machine that stops on an empty tape, but $ Q $ does not stop on an empty tape, contradiction .

In addition $ Q (z) \neq loop$ since clearly an empty tape is not being entered. We conclude that $ M (n) $ does not exist.

This is correct?