Turing equivalence
Encyclopedia
Turing equivalence may refer to:
See Turing machine equivalents
.
- Turing completenessTuring completenessIn computability theory, a system of data-manipulation rules is said to be Turing complete or computationally universal if and only if it can be used to simulate any single-taped Turing machine and thus in principle any computer. A classic example is the lambda calculus...
, having computational power equivalent to a universal Turing machine - Turing degreeTuring degreeIn computer science and mathematical logic the Turing degree or degree of unsolvability of a set of natural numbers measures the level of algorithmic unsolvability of the set...
equivalence (of sets), having the same level of unsolvability
See Turing machine equivalents
Turing machine equivalents
The following article is a referral from the article Turing machine. Many of the machines described here have articles that offer much more information.- Machines equivalent to the Turing machine model :Turing equivalence:...
.