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

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”