0
$\begingroup$

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.

Improve this question
$\endgroup$
3
  • 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, 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 ♦
    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
    Jun 6, 2017 at 22:40

1 Answer 1

Reset to default
-1
$\begingroup$

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

Improve this answer
$\endgroup$

Your Answer

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

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