I have seen many examples of universal Turing machines, all of which are undecidable due to the undecidability of the halting problem. I have also seen proofs that certain really small Turing machines are decidable and therefore not universal. I have also seen Turing machines that provably do simple enough calculations that they are not universal. It seems that every Turing machine is either complex enough to be universal or simple enough to be decidable.

My question is if there is a Turing machine that lives on this line, namely, is undecidable but provably not universal? (Related question: How would you even prove that such a machine was not universal under those conditions?)

  • 1
    $\begingroup$ Yes, there are such machines. Soare's book on computable sets and degrees is a good reference to learn about them. $\endgroup$ – Andrés E. Caicedo Apr 8 '14 at 4:57

You can easily built a Turing machine M such that $$M(x)=0 \mbox{ if } M_x(x) \mbox{ else do not halt} $$

It's not universal, as it always return $0$, but you can't decide if $M$ halts.

For more complex example that do not use any universal machine (here we use it as we simulate $M_x(x)$), you need much more knowledge about Turing degrees and Post's problem. The difficulty comes from the fact that most natural definitions of undecidable lead to something that are equivalent to the halting problem (and so semi-decidable) or more complex (but on a single machine, you can't have such a thing).

To my point of view, this is an informal consequence of the Rice's theorem. That's why the Post's problem was so hard to solve and its proof require some new tools like the priority method.

So the answer is "Yes, there are". But if you really want to deeply understand that answer, you need to learn what are Turing's Degree, Post's problem and its proof.

| cite | improve this answer | |

Your Answer

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

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