# Is Turing-completeness decidable?

This may be a silly question, but is there an algorithm that decides whether any given model of computation is Turing complete?

-
I think you would need a well-defined way to encode a model of computation as input for (say) a Turing machine. Any thoughts on how you would do that? – Hew Wolff Feb 8 '13 at 4:07
Well for starters, we could restrict ourselves to Turing machine inputs, and test for universality. But no, i cant see how to do this for an arbitrary model of computation. – goblin Feb 8 '13 at 4:11

No, there is no such algorithm. The notion of "Turing complete model of computation" is an informal one. We can recognize that many particular models of computation are Turing complete, in the sense that they can compute the same number-theoretic functions as a Turing machine. But there is no precise definition of a "model of computation"; there are many models of computation that differ in almost every respect. And what it means for one model to "compute a function" can be very different from what it means for another model to "compute a function". For example, we would say that all of the following are "Turing complete":

• Turing machines
• $\mu$ recursive functions
• The C programming language
• Conway's game of life

When we prove a specific model of computation is Turing complete, we have to first figure out exactly what that rigorous claim should mean in the context of our model; for different models we end up proving different things, but we interpret all of them as showing that the system is "Turing complete".

-

Following your "test for universality" suggestion: By Rice's theorem, there cannot be any algorithm that determines if a Turing machine is universal.

-