Turing-équivalent
- Turing-équivalent
-
Désigne un système strictement Turing-complet, c'est-à-dire, pouvant calculer exactement le même ensemble de fonctions que les machines de Turing (les fonctions calculables), sans plus.
Un système non Turing-equivalent ne semble pas pouvoir exister (voir hypercalcul). En effet, il nécessiterait que l'univers soit lui-même non Turing-équivalent ou que le temps ou l'information soit infiniment compressible.
Wikimedia Foundation.
2010.
Contenu soumis à la licence CC-BY-SA. Source : Article Turing-équivalent de Wikipédia en français (auteurs)
Regardez d'autres dictionnaires:
Turing machine equivalents — Turing machine(s) Machina Universal Turing machine Alternating Turing machine Quantum Turing machine Read only Turing machine Read only right moving Turing Machines Probabilistic Turing machine Multi track Turing machine Turing machine… … Wikipedia
Turing machine — For the test of artificial intelligence, see Turing test. For the instrumental rock band, see Turing Machine (band). Turing machine(s) Machina Universal Turing machine Alternating Turing machine Quantum Turing machine Read only Turing machine… … Wikipedia
Turing degree — Post s problem redirects here. For the other Post s problem , see Post s correspondence problem. In computer science and mathematical logic the Turing degree or degree of unsolvability of a set of natural numbers measures the level of algorithmic … Wikipedia
Turing completeness — For the usage of this term in the theory of relative computability by oracle machines, see Turing reduction. In computability theory, a system of data manipulation rules (such as an instruction set, a programming language, or a cellular… … Wikipedia
Turing reduction — In computability theory, a Turing reduction from a problem A to a problem B, named after Alan Turing, is a reduction which solves A, assuming B is already known (Rogers 1967, Soare 1987). It can be understood as an algorithm that could be used to … Wikipedia
Turing jump — In computability theory, the Turing jump or Turing jump operator, named for Alan Turing, is intuitively described as an operation that assigns to each decision problem X a successively harder decision problem X prime; with the property that X… … Wikipedia
Turing degree — noun Given a set of natural numbers, a measure of the level of algorithmic unsolvability of the set. See Also: Turing equivalent … Wiktionary
Turing equivalence — may refer to:* Turing completeness, having computational power equivalent to a universal Turing machine * Turing degree equivalence (of sets), having the same level of unsolvability … Wikipedia
Turing test — dablink|For the Doctor Who novel named after the test, see The Turing Test (novel).For the opera named after the test, see under the composer, Julian Wagstaff.The Turing test is a proposal for a test of a machine s ability to demonstrate… … Wikipedia
Turing's proof — First published in January 1937 with the title On Computable Numbers, With an Application to the Entscheidungsproblem , Turing s proof was the second proof of the assertion (Alonzo Church proof was first) that some questions are undecidable :… … Wikipedia
