Is Turing-completeness decidable?

Question

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

Answer 1

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".