Réduction de Turing - Turing reduction

Dans la théorie de la calculabilité , une réduction de Turing d'un problème de décision à un problème de décision est une machine d'oracle qui décide un problème étant donné un oracle pour (Rogers 1967, Soare 1987). Il peut être compris comme un algorithme qui pourrait être utilisé pour résoudre s'il disposait d'un sous - programme pour résoudre B . Le concept peut être appliqué de manière analogue aux problèmes de fonction . ${\style d'affichage A}$${\style d'affichage B}$${\style d'affichage A}$${\style d'affichage B}$${\style d'affichage A}$

Si une réduction de Turing de à existe, alors chaque algorithme pour peut être utilisé pour produire un algorithme pour , en insérant l'algorithme pour à chaque endroit où la machine informatique oracle interroge l'oracle pour . Cependant, étant donné que la machine oracle peut interroger l'oracle un grand nombre de fois, l'algorithme résultant peut nécessiter plus de temps asymptotiquement que l'algorithme ou l'oracle machine computing . Une réduction de Turing dans laquelle la machine oracle s'exécute en temps polynomial est connue sous le nom de réduction de Cook . ${\style d'affichage A}$${\style d'affichage B}$${\style d'affichage B}$${\style d'affichage A}$${\style d'affichage B}$${\style d'affichage A}$${\style d'affichage B}$${\style d'affichage B}$${\style d'affichage A}$

La première définition formelle de la calculabilité relative, alors appelée réductibilité relative, a été donnée par Alan Turing en 1939 en termes de machines oracle . Plus tard, en 1943 et 1952, Stephen Kleene a défini un concept équivalent en termes de fonctions récursives . En 1944, Emil Post a utilisé le terme « réductibilité de Turing » pour désigner le concept.

Définition

Étant donné deux ensembles de nombres naturels, nous disons que Turing est réductible à et écrivons ${\displaystyle A,B\subseteq \mathbb {N} }$${\style d'affichage A}$${\style d'affichage B}$

${\displaystyle A\leq _{T}B}$

s'il existe une machine oracle qui calcule la fonction caractéristique de A lorsqu'elle est exécutée avec oracle B . Dans ce cas, nous disons également que A est B -récursif et B -calculable .

S'il existe une machine oracle qui, lorsqu'elle est exécutée avec oracle B , calcule une fonction partielle avec le domaine A , alors A est dit B - énumérable récursivement et B - énumérable de manière calculable .

Nous disons que Turing est équivalent à et écrivons si les deux et Les classes d'équivalence des ensembles équivalents de Turing sont appelées degrés de Turing . Le degré de Turing d'un ensemble s'écrit . ${\style d'affichage A}$${\style d'affichage B}$${\displaystyle A\equiv _{T}B\,}$${\displaystyle A\leq _{T}B}$${\displaystyle B\leq _{T}A.}$${\style d'affichage X}$${\displaystyle {\textbf {deg}}(X)}$

Étant donné un ensemble , un ensemble est appelé Turing dur pour si pour tous . Si en plus , puis est appelé Turing complet pour . ${\displaystyle {\mathcal {X}}\subseteq {\mathcal {P}}(\mathbb {N} )}$${\displaystyle A\subseteq \mathbb {N} }$${\displaystyle {\mathcal {X}}}$${\displaystyle X\leq _{T}A}$${\displaystyle X\in {\mathcal {X}}}$${\displaystyle A\in {\mathcal {X}}}$${\style d'affichage A}$${\displaystyle {\mathcal {X}}}$

Relation entre la complétude de Turing et l'universalité computationnelle

La complétude de Turing, telle qu'elle vient d'être définie ci-dessus, ne correspond que partiellement à la complétude de Turing au sens d'universalité computationnelle. Plus précisément, une machine de Turing est une machine de Turing universelle si son problème d'arrêt (c'est-à-dire l'ensemble des entrées pour lesquelles elle s'arrête finalement) est complet plusieurs-un . Ainsi, une condition nécessaire mais insuffisante pour qu'une machine soit informatiquement universelle, est que le problème d'arrêt de la machine soit Turing-complet pour l'ensemble des ensembles récursivement énumérables. ${\displaystyle {\mathcal {X}}}$

Exemple

Notons l'ensemble des valeurs d'entrée pour lesquelles la machine de Turing d'indice e s'arrête. Alors les ensembles et sont équivalents à Turing ( dénote ici une fonction d'appariement efficace). Une réduction montrant peut être construite en utilisant le fait que . Etant donné un couple , un nouvel indice peut être construit en utilisant le théorème s _mn tel que le programme codé par ignore son entrée et se contente de simuler le calcul de la machine d'indice e sur l'entrée n . En particulier, la machine avec index s'arrête à chaque entrée ou s'arrête sur aucune entrée. Ainsi vaut pour tout e et n . Parce que la fonction i est calculable, cela montre . Les réductions présentées ici ne sont pas seulement des réductions de Turing, mais des réductions multiples , discutées ci-dessous. ${\displaystyle W_{e}}$${\displaystyle A=\{e\mid e\in W_{e}\}}$${\displaystyle B=\{(e,n)\mid n\in W_{e}\}}$${\style d'affichage (-,-)}$${\displaystyle A\leq _{T}B}$${\displaystyle e\in A\Leftrightarrow (e,e)\in B}$${\style d'affichage (e,n)}$${\style d'affichage i(e,n)}$${\style d'affichage i(e,n)}$${\style d'affichage i(e,n)}$${\displaystyle i(e,n)\in A\Leftrightarrow (e,n)\in B}$${\displaystyle B\leq _{T}A}$

Propriétés

• Chaque ensemble est Turing équivalent à son complément.
• Chaque ensemble calculable est Turing réductible à tout autre ensemble. Parce que tout ensemble calculable peut être calculé sans oracle, il peut être calculé par une machine oracle qui ignore l'oracle donné.
• La relation est transitive : si et alors . De plus, est valable pour tout ensemble A , et donc la relation est un préordre (ce n'est pas un ordre partiel car et n'implique pas nécessairement ).${\displaystyle \leq _{T}}$${\displaystyle A\leq _{T}B}$${\displaystyle B\leq _{T}C}$${\displaystyle A\leq _{T}C}$${\displaystyle A\leq _{T}A}$${\displaystyle \leq _{T}}$${\displaystyle A\leq _{T}B}$${\displaystyle B\leq _{T}A}$${\style d'affichage A=B}$
• Il existe des couples d'ensembles tels que A n'est pas Turing réductible à B et B n'est pas Turing réductible à A . Ce n'est donc pas une commande totale .${\style d'affichage (A,B)}$${\displaystyle \leq _{T}}$
• Il existe des suites décroissantes infinies d'ensembles sous . Cette relation n'est donc pas fondée .${\displaystyle \leq _{T}}$
• Chaque ensemble est Turing réductible à son propre saut de Turing , mais le saut de Turing d'un ensemble n'est jamais réductible à l'ensemble original.

L'utilisation d'une réduction

Étant donné que chaque réduction d'un ensemble à un ensemble doit déterminer si un seul élément se trouve en un nombre fini d'étapes, il ne peut effectuer qu'un nombre fini de requêtes d'appartenance à l'ensemble . Lorsque la quantité d'informations sur l'ensemble utilisé pour calculer un seul bit de est discutée, cela est précisé par la fonction use. Formellement, l' utilisation d'une réduction est la fonction qui envoie chaque nombre naturel au plus grand nombre naturel dont l'appartenance à l'ensemble B a été interrogée par la réduction tout en déterminant l'appartenance de à . ${\style d'affichage B}$${\style d'affichage A}$${\style d'affichage A}$${\style d'affichage B}$${\style d'affichage B}$${\style d'affichage A}$${\style d'affichage n}$${\style d'affichage m}$${\style d'affichage n}$${\style d'affichage A}$

Des réductions plus fortes

Il existe deux manières courantes de produire des réductions plus fortes que la réductibilité de Turing. La première consiste à limiter le nombre et la manière des requêtes Oracle.

• Set est plusieurs-un réductible à s'il existe une fonction calculable totale telle qu'un élément est dans si et seulement si est dans . Une telle fonction peut être utilisée pour générer une réduction de Turing (en calculant , en interrogeant l'oracle, puis en interprétant le résultat).${\style d'affichage A}$${\style d'affichage B}$ ${\style d'affichage f}$${\style d'affichage n}$${\style d'affichage A}$${\style d'affichage f(n)}$${\style d'affichage B}$${\style d'affichage f(n)}$
• Une réduction de table de vérité ou une réduction de table de vérité faible doit présenter toutes ses requêtes Oracle en même temps. Dans une réduction de table de vérité, la réduction donne également une fonction booléenne (une table de vérité ) qui, une fois donnée les réponses aux requêtes, produira la réponse finale de la réduction. Dans une réduction de table de vérité faible, la réduction utilise les réponses d'oracle comme base pour un calcul ultérieur en fonction des réponses données (mais n'utilise pas l'oracle). De manière équivalente, une réduction de table de vérité faible est une réduction pour laquelle l'utilisation de la réduction est bornée par une fonction calculable. Pour cette raison, les réductions de table de vérité faibles sont parfois appelées réductions de Turing « bornées ».

La deuxième façon de produire une notion de réductibilité plus forte est de limiter les ressources de calcul que le programme implémentant la réduction de Turing peut utiliser. Ces limites sur la complexité calculatoire de la réduction sont importantes lors de l'étude de classes subrécursives telles que P . Un ensemble A est réductible en temps polynomial à un ensemble s'il y a une réduction de Turing de à qui s'exécute en temps polynomial. Le concept de réduction de l'espace log est similaire. ${\style d'affichage B}$${\style d'affichage A}$${\style d'affichage B}$

Ces réductions sont plus fortes dans le sens où elles permettent une distinction plus fine en classes d'équivalence et satisfont à des exigences plus restrictives que les réductions de Turing. Par conséquent, de telles réductions sont plus difficiles à trouver. Il n'y a peut-être aucun moyen de construire une réduction plusieurs-un d'un ensemble à un autre même lorsqu'une réduction de Turing existe pour les mêmes ensembles.

Réductions plus faibles

Selon la thèse de Church-Turing , une réduction de Turing est la forme la plus générale d'une réduction effectivement calculable. Néanmoins, des réductions plus faibles sont également envisagées. Set est dit arithmétique dans si est définissable par une formule d' arithmétique de Peano avec comme paramètre. L'ensemble est hyperarithmétique dans s'il existe un ordinal récursif tel qui est calculable à partir de , le saut de Turing -itéré de . La notion de constructibilité relative est une notion de réductibilité importante en théorie des ensembles. ${\style d'affichage A}$ ${\style d'affichage B}$${\style d'affichage A}$${\style d'affichage B}$${\style d'affichage A}$ ${\style d'affichage B}$ ${\style d'affichage \alpha }$${\style d'affichage A}$${\style d'affichage B^{(\alpha )}}$${\style d'affichage B}$

Voir également

• Réduction de Karp

Remarques

Les références

• M. Davis, éd., 1965. The Undecidable—Basic Papers on Undecidable Propositions, Unsolvable Problems and Computable Functions , Raven, New York. Réimpression, Douvres, 2004. ISBN  0-486-43228-9 .
• SC Kleene, 1952. Introduction aux métamathématiques. Amsterdam : Hollande du Nord.
• SC Kleene et EL Post, 1954. "Le semi-réseau supérieur des degrés d'insolvabilité récursive". Annales de mathématiques v. 2 n. 59, 379-407.
• Poste, EL (1944). "Ensembles récursivement énumérables d'entiers positifs et leurs problèmes de décision" ( PDF ) . Bulletin de la Société mathématique américaine . 50 : 284-316. doi : 10.1090/s0002-9904-1944-08111-1 . Récupéré le 17/12/2015 .
• A. Turing, 1939. "Systèmes de logique basés sur des ordinaux." Actes de la London Mathematics Society , ser. 2 v. 45, p. 161-228. Réimprimé dans "The Undecidable", M. Davis éd., 1965.
• H. Rogers, 1967. Théorie des fonctions récursives et calculabilité effective. McGraw-Hill.
• R. Soare, 1987. Ensembles et degrés récursivement énumérables, Springer.
• Davis, Martin (novembre 2006). « Qu'est-ce que la réductibilité de Turing ? » ( PDF ) . Avis de l'American Mathematical Society . 53 (10) : 1218-1219 . Récupéré le 2008-01-16 .

Liens externes

• Dictionnaire des algorithmes et des structures de données du NIST : réduction de Turing