Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
1  
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. –  user18921 Feb 8 '13 at 4:11
add comment

2 Answers

up vote 1 down vote accepted

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

share|improve this answer
add comment

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

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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