gotchaMinor
Explain the difference between Turing Complete and Turing Equivalence
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?
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.
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.