Degré de Turing

En informatique et en logique mathématique, le degré de Turing (nommé d'après Alan Turing) ou le degré d'insolubilité d'un ensemble d'entiers naturels mesure le niveau d'insolubilité algorithmique de l'ensemble. Le concept de degré de Turing est fondamental dans la théorie de la calculabilité, où des ensembles d'entiers naturels sont souvent considérés comme des problèmes de décision. Le degré de Turing d'un ensemble révèle combien il est difficile de résoudre le problème de décision associé à cet ensemble, à savoir, déterminer si un nombre arbitraire est dans l'ensemble donné. Deux ensembles sont Turing-équivalents s'ils ont le même niveau d’insolvabilité ; chaque degré de Turing est une collection d'ensembles Turing-équivalents, de sorte que deux ensembles ayant un degré de Turing différent ne sont pas Turing-équivalent. En outre, les degrés de Turing sont partiellement ordonnés de telle sorte que si le degré de Turing d'un ensemble X est inférieur au degré de Turing d'un ensemble Y, alors toute procédure (récursive) qui décide correctement si les nombres sont dans Y peut être efficacement convertie en une procédure qui décide correctement si les nombres sont dans X. Ainsi, le degré de Turing d'un ensemble correspond à son niveau d'insolubilité algorithmique. Les degrés de Turing ont été introduits par Emil Leon Post (1944), et de nombreux résultats fondamentaux ont été établis par Stephen Cole Kleene et Post (1954). Les degrés de Turing ont dès lors été un domaine de recherche intense. Pour l'ensemble de cet article, le mot ensemble fera référence à un ensemble d'entiers naturels. Un ensemble X est dit Turing-réductible à un ensemble Y s'il y a un oracle qui décide l'appartenance dans X quand un oracle décide de l'appartenance dans Y. La notation X ≤T Y indique que X est Turing-réductible à Y. Deux ensembles X et Y sont définis Turing-équivalents si X est Turing-réductible à Y et Y est Turing-réductible à X. La notation X ≡T Y indique que X et Y sont Turing-équivalents.

À propos de ce résultat

Cette page est générée automatiquement et peut contenir des informations qui ne sont pas correctes, complètes, à jour ou pertinentes par rapport à votre recherche. Il en va de même pour toutes les autres pages de ce site. Veillez à vérifier les informations auprès des sources officielles de l'EPFL.

Publications associées (17)

Concepts associés (13)

Cours associés (1)

Séances de cours associées (8)

Algorithmes et croissance des fonctions CS-101: Advanced information, computation, communication I

Couvre les algorithmes d'optimisation, l'appariement stable et la notation Big-O pour l'efficacité de l'algorithme.

Halting Problem : des problèmes insolubles CS-101: Advanced information, computation, communication I

Explore le problème de l'arrêt, démontrant son insolvabilité et les limites des algorithmes.

Halting Problem : des problèmes insolubles CS-101: Advanced information, computation, communication I

Explore l'insolvabilité du problème d'arrêt dans les algorithmes et les limites des procédures dans la détermination de l'arrêt du programme.

vignette|L'animation illustre une machine impossible : il n'y a pas de machine qui lit n'importe quel code source d'un programme et dit si son exécution termine ou non. En théorie de la calculabilité, le problème de l'arrêt est le problème de décision qui détermine, à partir d'une description d'un programme informatique, et d'une entrée, si le programme s'arrête avec cette entrée ou non.

In computability theory, a Turing reduction from a decision problem to a decision problem is an oracle machine which decides problem given an oracle for (Rogers 1967, Soare 1987). It can be understood as an algorithm that could be used to solve if it had available to it a subroutine for solving . The concept can be analogously applied to function problems. If a Turing reduction from to exists, then every algorithm for can be used to produce an algorithm for , by inserting the algorithm for at each place where the oracle machine computing queries the oracle for .

In computability theory and computational complexity theory, a many-one reduction (also called mapping reduction) is a reduction which converts instances of one decision problem (whether an instance is in ) to another decision problem (whether an instance is in ) using an effective function. The reduced instance is in the language if and only if the initial instance is in its language . Thus if we can decide whether instances are in the language , we can decide whether instances are in its language by applying the reduction and solving .

MATH-483: Gödel and recursivity

Gödel incompleteness theorems and mathematical foundations of computer science

Complex Representation Learning with Graph Convolutional Networks for Knowledge Graph Alignment

Thanh Trung Huynh, Quoc Viet Hung Nguyen, Thành Tâm Nguyên

The task of discovering equivalent entities in knowledge graphs (KGs), so-called KG entity alignment, has drawn much attention to overcome the incompleteness problem of KGs. The majority of existing techniques learns the pointwise representations of entiti ...

London2023

A useful robot is one that fulfils its intended function. In a factory setting, where robots have been used successfully for decades, this function is often singular and clearly defined. Similarly, the surroundings of the robot are mostly known, sterile, a ...

EPFL2020

A Composition Theorem for Conical Juntas

Mika Tapani Göös

We describe a general method of proving degree lower bounds for conical juntas (nonnegative combinations of conjunctions) that compute recursively defined boolean functions. Such lower bounds are known to carry over to communication complexity. We give two ...

Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik GmbH, Wadern/Saarbruecken, Germany2016