HiveBrain v1.2.0
Get Started
← Back to all entries
gotchaMinor

Explain the difference between Turing Complete and Turing Equivalence

Submitted by: @import:stackexchange-cs··
0
Viewed 0 times
theanddifferencecompletebetweenturingexplainequivalence

Problem

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?

Solution

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.

Context

StackExchange Computer Science Q#134273, answer score: 7

Revisions (0)

No revisions yet.