5
$\begingroup$

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?

Improve this question
$\endgroup$
0

1 Answer 1

Reset to default
9
$\begingroup$

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

Improve this answer
$\endgroup$
3
  • 4
    $\begingroup$ If something was strictly more powerful than Turing Machines, I would describe it as Turing Hard, not Turing complete. $\endgroup$
    – Joey Eremondi
    Commented Feb 3, 2016 at 8:07
  • 2
    $\begingroup$ @jmite that's where the terminology works well for the complexity classes, but not for computability - NP-hard problems are at least as hard (in one of the English senses) as anything in NP. Turing-hard in that way doesn't jibe well with me. We do have of course "Turing-equivalent" for models that are Turing-complete but no stronger. $\endgroup$
    – Luke Mathieson
    Commented Feb 3, 2016 at 10:53
  • $\begingroup$ In this case I'll try to say only "Turing-equivalent" or "uncomputable" and avoid that term if possible, to those who don't know much about computability theory. $\endgroup$
    – user23013
    Commented Feb 3, 2016 at 12:17

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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