5
$\begingroup$

I'm not sure if I understand the difference between Turing Complete and Turing Equivalent programming languages.

A computational system that can compute every Turing-computable function is called Turing-complete (or Turing-powerful).

A Turing-complete system is called Turing-equivalent if every function it can compute is also Turing-computable; i.e., it computes precisely the same class of functions as do Turing machines.

I'm not sure if I understand the difference between these two terminologies properly and what "Turing-computable" means. So for example if I have a programming language $X$, it is Turing complete if it can do any and everything that a Turing Machine can do? And it $X$ ends up being Turing complete and it can be shown that all of the functions that it computes are Turing computable, then $X$ is also Turing equivalent?

$\endgroup$
1
  • 1
    $\begingroup$ There exist functions that can't be computed by TM. You can imagine some computational system that can magically compute more functions (e.g. Oracle machine). This system won't be Turing-equivalent. $\endgroup$
    – user114966
    Jan 12, 2021 at 15:46

1 Answer 1

6
$\begingroup$

A system is Turing-complete if it is at least as powerful as Turing machines.

A system is Turing-equivalent if it is exactly as powerful as Turing machines.

An example of a Turing-complete system which is not Turing equivalent is Turing machines with oracle access to an oracle for the halting problem.

One can come up with one additional definition to complete the picture: a system is effective if it is at most as powerful as Turing machines, that is, if every function computed by the system is computable by a Turing machine.

$\endgroup$

Your Answer

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

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