# An Undecidable but not Universal Turing Machine?

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?)

• Yes, there are such machines. Soare's book on computable sets and degrees is a good reference to learn about them. – 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).