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$ Commented Jun 6, 2017 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
    Commented Jun 6, 2017 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
    Commented Jun 6, 2017 at 22:40

1 Answer 1


Yes...your intuition to the problem approach is correct.Here are the properties from which you can gain much more clarity: Unsolvable Problems Stanford-Stanford University


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.