[Solved]: Is something more than Turing complete Turing complete?

Problem Detail: 

In complexity theory, we do not call a decision problem that is not in NP "NP-complete".

But in computability, do we call a machine model "Turing complete" if it can compute functions which Turing machines can not?

The definition from Wikipedia didn't address this problem explicitly, and likely assumed yes:

A computational system that can compute every Turing-computable function is called Turing complete (or Turing powerful). Alternatively, such a system is one that can simulate a universal Turing machine.

For example, if there is a system that can:

• Compute every Turing-computable function.
• Compute the halting problem for a Turing machine.

And nothing else. Is it Turing complete?

Asked By : user23013

Answered By : Luke Mathieson

Yes. The "complete" in NP-complete and in Turing-complete are two different notions.

For Turing-complete it means (as per the definition in the question) that the system can compute the complete (in the basic English sense) set of Turing computable functions (i.e. it can do at least everything a Turing Machine can).

For NP-complete, it's not obvious that the word has anything to do with its basic English meaning except perhaps in the tenuous sense that the problem has all the complexity inherent in the class, whatever that means.

Another way to express the difference is that NP-complete can be rephrased as "complete for the class NP", whereas Turing-complete does not mean "complete for the class R" (or RE).

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/52635