The definition of the universal Turing machine is

$$ U(\langle M \rangle,p)=M(p) $$

where U is a universal Turing taking two inputs $\langle M \rangle$, the binary encoding of a Turing machine, and $p$ a binary program.

What happens in the case where we feed the null Turing machine to the UTM.

$$ U(0,p)=?U(p)? $$

Will this give out the outputs that are specific to the given formulation of the UTM being run?

Also, is there any kind of general properties of $U(p)$ between the universal Turing machines? My intuition tells me $U(p)$ must be the same answer for all UTMs and all $p$, but I would like confirmation.

  • 1
    $\begingroup$ There is no null Turing machine. If the input is malformed, then we don't particularly care about what the UTM outputs. $\endgroup$ – Yuval Filmus Jun 6 '17 at 22:09
  • $\begingroup$ Given any "reasonable" encoding $\langle . \rangle$, $0$ is just the index of some machine. Which one depends on the specific encoding (there are infinitely many). Nothing special about it. $\endgroup$ – Raphael Jun 6 '17 at 22:10
  • $\begingroup$ @Yuval I see. Then my question should read a universal Turing machine simulating itself U(U,p) = U(p)? This would be equivalent to the null Turing machine as I meant it in my question. $\endgroup$ – Anon21 Jun 6 '17 at 22:40

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.