This may be a silly question, but is there an algorithm that decides whether any given model of computation is Turing complete?
- Anybody can ask a question
- Anybody can answer
- The best answers are voted up and rise to the top
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":
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.