Théorie de la calculabilité

À partir de la théorie des ensembles et fonctions récursifs décrite ci-dessus, le domaine de la théorie de la récursivité s’est développé pour inclure l’étude de nombreux sujets étroitement liés. Ce ne sont pas des domaines de recherche indépendants: chacun de ces domaines tire des idées et des résultats des autres, et la plupart des théoriciens de la récursivité connaissent la majorité d’entre eux.

Calculabilité relative et degré de Turingmodifier

La théorie de la récursivité en logique mathématique s’est traditionnellement concentrée sur la calculabilité relative, une généralisation de la calculabilité de Turing définie à l’aide de machines de Turing oracle, introduite par Turing (1939). Une machine de Turing oracle est un dispositif hypothétique qui, en plus d’effectuer les actions d’une machine de Turing régulière, est capable de poser des questions sur un oracle, qui est un ensemble particulier de nombres naturels. La machine oracle ne peut poser que des questions de la forme “N est-il dans l’ensemble oracle?”. Chaque question recevra immédiatement une réponse correcte, même si l’ensemble oracle n’est pas calculable. Ainsi, une machine oracle avec un oracle non calculable sera en mesure de calculer des ensembles qu’une machine de Turing sans oracle ne peut pas.

De manière informelle, un ensemble de nombres naturels A est Turing réductible à un ensemble B s’il existe une machine oracle qui indique correctement si les nombres sont dans A lorsqu’ils sont exécutés avec B comme ensemble oracle (dans ce cas, l’ensemble A est également dit (relativement) calculable à partir de B et récursif dans B). Si un ensemble A est Turing réductible à un ensemble B et B est Turing réductible à A, alors les ensembles sont dits avoir le même degré de Turing (également appelé degré d’insolvabilité). Le degré de Turing d’un ensemble donne une mesure précise de la non-compatibilité de l’ensemble.

Les exemples naturels d’ensembles qui ne sont pas calculables, y compris de nombreux ensembles différents qui codent des variantes du problème d’arrêt, ont deux propriétés en commun:

1. Ils sont récursivement énumérables, et
2. Chacun peut être traduit en n’importe quel autre via une réduction multiple. Autrement dit, étant donné de tels ensembles A et B, il existe une fonction totale calculable f telle que A = {x: f(x)∈ B}. Ces ensembles sont dits équivalents à plusieurs un (ou équivalents m).

Les réductions en plusieurs un sont “plus fortes” que les réductions de Turing: si un ensemble A est plusieurs un réductible à un ensemble B, alors A est Turing réductible à B, mais l’inverse ne tient pas toujours. Bien que les exemples naturels d’ensembles non calculables soient tous équivalents en plusieurs un, il est possible de construire récursivement des ensembles énumérables A et B tels que A soit Turing réductible à B mais pas plusieurs un réductibles à B. On peut montrer que chaque ensemble récursivement énumérable est réductible en plusieurs un au problème d’arrêt, et donc le problème d’arrêt est l’ensemble récursivement énumérable le plus compliqué en ce qui concerne la réductibilité en plusieurs un et en ce qui concerne la réductibilité de Turing. Post (1944) a demandé si chaque ensemble récursivement énumérable était soit calculable, soit équivalent à Turing au problème d’arrêt, c’est-à-dire s’il n’y avait pas d’ensemble récursivement énumérable avec un degré de Turing intermédiaire entre ces deux.

En tant que résultats intermédiaires, les types naturels post-définis d’ensembles récursivement énumérables comme les ensembles simples, hypersimple et hyperhypersimple. Post a montré que ces ensembles se situent strictement entre les ensembles calculables et le problème d’arrêt en ce qui concerne la réductibilité à plusieurs. Post a également montré que certains d’entre eux sont strictement intermédiaires sous d’autres notions de réductibilité plus fortes que la réductibilité de Turing. Mais Post a laissé ouvert le problème principal de l’existence d’ensembles récursivement énumérables de degré de Turing intermédiaire; ce problème est devenu connu sous le nom de problème de Post. Après dix ans, Kleene et Post ont montré en 1954 qu’il existe des degrés de Turing intermédiaires entre ceux des ensembles calculables et le problème d’arrêt, mais ils n’ont pas réussi à montrer qu’aucun de ces degrés contient un ensemble récursivement énumérable. Très peu de temps après, Friedberg et Muchnik ont résolu indépendamment le problème de Post en établissant l’existence d’ensembles récursivement énumérables de degré intermédiaire. Ce résultat révolutionnaire a ouvert une vaste étude des degrés de Turing des ensembles récursivement énumérables qui se sont avérés posséder une structure très compliquée et non triviale.

Il y a un nombre incalculable d’ensembles qui ne sont pas récursivement énumérables, et l’investigation des degrés de Turing de tous les ensembles est aussi centrale dans la théorie de la récursivité que l’investigation des degrés de Turing récursivement énumérables. De nombreux degrés avec des propriétés spéciales ont été construits: degrés sans hyperimmunité où chaque fonction calculable par rapport à ce degré est majorisée par une fonction calculable (non corrigée); degrés élevés par rapport auxquels on peut calculer une fonction f qui domine toute fonction calculable g en ce sens qu’il existe une constante c dépendant de g telle que g(x) < f(x) pour tous x > c; degrés aléatoires contenant des ensembles algorithmiquement aléatoires; 1- degrés génériques d’ensembles 1-génériques; et les degrés en dessous du problème d’arrêt des ensembles récursifs limites.

L’étude des degrés de Turing arbitraires (pas nécessairement récursivement énumérables) implique l’étude du saut de Turing. Étant donné un ensemble A, le saut de Turing de A est un ensemble de nombres naturels codant une solution au problème d’arrêt pour les machines de Turing oracle fonctionnant avec oracle A. Le saut de Turing de tout ensemble est toujours de degré de Turing supérieur à l’ensemble d’origine, et un théorème de Friedburg montre que tout ensemble qui calcule le problème d’arrêt peut être obtenu comme le saut de Turing d’un autre ensemble. Le théorème de Post établit une relation étroite entre l’opération de saut de Turing et la hiérarchie arithmétique, qui est une classification de certains sous-ensembles des nombres naturels en fonction de leur définissabilité en arithmétique.

De nombreuses recherches récentes sur les degrés de Turing se sont concentrées sur la structure globale de l’ensemble des degrés de Turing et de l’ensemble des degrés de Turing contenant des ensembles récursivement énumérables. Un théorème profond de Shore et Slaman (1999) stipule que la fonction mappant un degré x au degré de son saut de Turing est définissable dans l’ordre partiel des degrés de Turing. Une enquête récente d’Ambos-Spies et Fejer (2006) donne un aperçu de cette recherche et de son évolution historique.

Autres réductionsmodiFier

Un domaine de recherche en théorie de la récursivité étudie les relations de réductibilité autres que la réductibilité de Turing. Post (1944) a introduit plusieurs réductibilité fortes, ainsi nommées parce qu’elles impliquent une réductibilité de la table de vérité. Une machine de Turing implémentant une forte réductibilité calculera une fonction totale quel que soit l’oracle avec lequel elle est présentée. Les réducibilités faibles sont celles où un processus de réduction peut ne pas se terminer pour tous les oracles; la réductibilité de Turing en est un exemple.

Les réductibles fortes comprennent:

La réductibilité un-un A est réductible un-un (ou 1-réductible) à B s’il existe une fonction injective totale calculable f telle que chaque n est dans A si et seulement si f(n) est dans B. Réductibilité multiple C’est essentiellement une réductibilité un-un sans la contrainte que f soit injective. A est plusieurs-un réductible (ou m-réductible) à B s’il existe une fonction totale calculable f telle que chaque n est dans A si et seulement si f(n) est dans B. La réductibilité de la table de vérité A est une table de vérité réductible à B si A est réductible à B via une machine de Turing oracle qui calcule une fonction totale quel que soit l’oracle qui lui est donné. En raison de la compacité de l’espace de Cantor, cela équivaut à dire que la réduction présente une seule liste de questions (en fonction uniquement de l’entrée) à l’oracle simultanément, puis après avoir vu leurs réponses est capable de produire une sortie sans poser de questions supplémentaires quelle que soit la réponse de l’oracle aux requêtes initiales. De nombreuses variantes de réductibilité de la table de vérité ont également été étudiées.

D’autres réductibles (positives, disjonctives, conjonctives, linéaires et leurs versions faibles et bornées) sont discutées dans l’article Réduction (théorie de la récursivité).

La recherche majeure sur les réducibilités fortes a été de comparer leurs théories, tant pour la classe de tous les ensembles récursivement énumérables que pour la classe de tous les sous-ensembles des nombres naturels. De plus, les relations entre les réductibles ont été étudiées. Par exemple, on sait que chaque degré de Turing est soit un degré de la table de vérité, soit l’union d’une infinité de degrés de la table de vérité.

Des réductibilité plus faibles que la réductibilité de Turing (c’est-à-dire des réductibilité impliquées par la réductibilité de Turing) ont également été étudiées. Les plus connues sont la réductibilité arithmétique et la réductibilité hyperarithmétique. Ces réductibilité sont étroitement liées à la définissabilité sur le modèle standard de l’arithmétique.

Le théorème de Rice et la hiérarchie arithmétiquedit

Rice a montré que pour chaque classe non triviale C (qui contient certains ensembles r.e. mais pas tous), l’ensemble d’index E = {e: l’eth r.e. l’ensemble We est en C} a la propriété que le problème d’arrêt ou son complément est réductible en plusieurs un à E, c’est-à-dire qu’il peut être mappé en utilisant une réduction en plusieurs un à E (voir le théorème de Rice pour plus de détails). Mais, beaucoup de ces ensembles d’index sont encore plus compliqués que le problème d’arrêt. Ces types d’ensembles peuvent être classés à l’aide de la hiérarchie arithmétique. Par example, l’ensemble d’index FIN de la classe de tous les ensembles finis est au niveau Σ2, l’ensemble d’index REC de la classe de tous les ensembles récursifs est au niveau Σ3, l’ensemble d’index COFIN de tous les ensembles cofinites est également au niveau Σ3 et l’ensemble d’index COMP de la classe de tous les ensembles complets de Turing Σ4. Ces niveaux hiérarchiques sont définis de manière inductive, Σn+1 ne contient que tous les ensembles récursivement énumérables par rapport à Σn ; Σ1 contient les ensembles récursivement énumérables. Les ensembles d’index donnés ici sont même complets pour leurs niveaux, c’est-à-dire que tous les ensembles de ces niveaux peuvent être réduits en plusieurs-un aux ensembles d’index donnés.

Mathématiques inverses

Le programme de mathématiques inverses demande quels axiomes d’existence d’ensembles sont nécessaires pour prouver des théorèmes particuliers des mathématiques dans des sous-systèmes d’arithmétique du second ordre. Cette étude a été initiée par Harvey Friedman et a été étudiée en détail par Stephen Simpson et d’autres; Simpson (1999) donne une discussion détaillée du programme. Les axiomes d’existence d’ensemble en question correspondent de manière informelle à des axiomes disant que l’ensemble des puissances des nombres naturels est fermé sous diverses notions de réductibilité. L’axiome de ce type le plus faible étudié en mathématiques inverses est la compréhension récursive, qui stipule que l’ensemble des puissances des naturels est fermé sous la réductibilité de Turing.

NumberingsEdit

Une numérotation est une énumération de fonctions; elle a deux paramètres, e et x et délivre la valeur de la e-th fonction dans la numérotation sur l’entrée x. Les numérotations peuvent être récursives partielles bien que certains de ses membres soient récursifs totaux, c’est-à-dire des fonctions calculables. Les numéros admissibles sont ceux dans lesquels tous les autres peuvent être traduits. Une numérotation de Friedberg (du nom de son découvreur) est une numérotation un-un de toutes les fonctions récursives partielles; ce n’est nécessairement pas une numérotation admissible. Des recherches ultérieures ont également traité des numérotations d’autres classes comme des classes d’ensembles récursivement énumérables. Goncharov a découvert par exemple une classe d’ensembles récursivement énumérables pour lesquels les numérotations se divisent en exactement deux classes par rapport aux isomorphismes récursifs.

La méthode de prioritédit

Pour plus d’explications, voir la section Problème de l’article et la méthode de priorité dans l’article Degré de Turing.

Le problème de Post a été résolu avec une méthode appelée méthode prioritaire ; une preuve utilisant cette méthode est appelée argument prioritaire. Cette méthode est principalement utilisée pour construire des ensembles énumérables récursivement avec des propriétés particulières. Pour utiliser cette méthode, les propriétés souhaitées de l’ensemble à construire sont divisées en une liste infinie d’objectifs, appelés exigences, de sorte que la satisfaction de toutes les exigences fera que l’ensemble construit aura les propriétés souhaitées. Chaque exigence est attribuée à un nombre naturel représentant la priorité de l’exigence; donc 0 est attribué à la priorité la plus importante, 1 à la deuxième plus importante, et ainsi de suite. L’ensemble est ensuite construit par étapes, chaque étape essayant de satisfaire à l’une des exigences en ajoutant des nombres à l’ensemble ou en interdisant des nombres de l’ensemble afin que l’ensemble final satisfasse à l’exigence. Il peut arriver que la satisfaction d’une exigence entraîne l’insatisfaction d’une autre; l’ordre de priorité est utilisé pour décider quoi faire dans un tel événement.

Des arguments de priorité ont été utilisés pour résoudre de nombreux problèmes en théorie de la récursivité et ont été classés dans une hiérarchie basée sur leur complexité (Soare 1987). Parce que les arguments prioritaires complexes peuvent être techniques et difficiles à suivre, il a traditionnellement été considéré comme souhaitable de prouver des résultats sans arguments prioritaires, ou de voir si les résultats prouvés avec des arguments prioritaires peuvent également être prouvés sans eux. Par exemple, Kummer a publié un article sur une preuve de l’existence de numérotations de Friedberg sans utiliser la méthode de priorité.

Le réseau des ensembles récursivement énumérables

Lorsque Post a défini la notion d’un ensemble simple comme un ensemble r.e. avec un complément infini ne contenant aucun r.e. infini. ensemble, il a commencé à étudier la structure des ensembles récursivement énumérables sous inclusion. Ce treillis est devenu une structure bien étudiée. Les ensembles récursifs peuvent être définis dans cette structure par le résultat de base qu’un ensemble est récursif si et seulement si l’ensemble et son complément sont tous deux récursivement énumérables. Les ensembles r.e. infinis ont toujours des sous-ensembles récursifs infinis; mais d’un autre côté, des ensembles simples existent mais n’ont pas de surensemble récursif coinfinite. Post (1944) a introduit des ensembles déjà hypersimple et hyperhypersimple; des ensembles maximaux ultérieurs ont été construits qui sont des ensembles r.e. tels que chaque r.e. le surensemble est soit une variante finie de l’ensemble maximal donné, soit est co-fini. La motivation initiale de Post dans l’étude de ce réseau était de trouver une notion structurelle telle que chaque ensemble qui satisfait cette propriété n’est ni dans le degré de Turing des ensembles récursifs ni dans le degré de Turing du problème d’arrêt. Post n’a pas trouvé une telle propriété et la solution à son problème a plutôt appliqué des méthodes prioritaires; Harrington et Soare (1991) ont finalement trouvé une telle propriété.

Problèmes d’automorphismemodifier

Une autre question importante est l’existence d’automorphismes dans les structures récursives-théoriques. L’une de ces structures est celle d’un ensemble récursivement énumérable sous inclusion modulo différence finie; dans cette structure, A est inférieur à B si et seulement si la différence d’ensemble B−A est finie. Les ensembles maximaux (tels que définis dans le paragraphe précédent) ont la propriété qu’ils ne peuvent pas être automorphes à des ensembles non maximaux, c’est-à-dire que s’il existe un automorphisme des ensembles énumérables récursifs sous la structure qui vient d’être mentionnée, alors chaque ensemble maximal est mappé à un autre ensemble maximal. Soare (1974) a montré que l’inverse est également valable, c’est-à-dire que tous les deux ensembles maximaux sont automorphes. Ainsi, les ensembles maximaux forment une orbite, c’est-à-dire que chaque automorphisme préserve la maximalité et que deux ensembles maximaux quelconques sont transformés l’un en l’autre par un automorphisme. Harrington a donné un autre exemple de propriété automorphe : celle des ensembles créatifs, les ensembles qui sont plusieurs équivalents au problème d’arrêt.

Outre le réseau des ensembles récursivement énumérables, les automorphismes sont également étudiés pour la structure des degrés de Turing de tous les ensembles ainsi que pour la structure des degrés de Turing des ensembles r.e. Dans les deux cas, Cooper prétend avoir construit des automorphismes non triviaux qui mappent certains degrés à d’autres degrés; cette construction n’a cependant pas été vérifiée et certains collègues pensent que la construction contient des erreurs et que la question de savoir s’il existe un automorphisme non trivial des degrés de Turing reste l’une des principales questions non résolues dans ce domaine (Slaman et Woodin 1986, Ambos-Spies et Fejer 2006).

Complexité de Kolmogorovmodifier

Le domaine de la complexité de Kolmogorov et de l’aléatoire algorithmique a été développé au cours des années 1960 et 1970 par Chaitin, Kolmogorov, Levin, Martin-Löf et Solomonoff (les noms sont donnés ici par ordre alphabétique; une grande partie de la recherche était indépendante et l’unité du concept d’aléatoire n’était pas comprise à l’époque). L’idée principale est de considérer une machine de Turing universelle U et de mesurer la complexité d’un nombre (ou chaîne) x comme la longueur de l’entrée la plus courte p telle que U(p) produise x. Cette approche a révolutionné les façons antérieures de déterminer quand une séquence infinie (de manière équivalente, fonction caractéristique d’un sous-ensemble des nombres naturels) est aléatoire ou non en invoquant une notion d’aléatoire pour les objets finis. La complexité de Kolmogorov est devenue non seulement un sujet d’étude indépendant, mais est également appliquée à d’autres sujets comme outil d’obtention de preuves.Il y a encore beaucoup de problèmes ouverts dans ce domaine. Pour cette raison, une récente conférence de recherche dans ce domaine a eu lieu en janvier 2007 et une liste de problèmes ouverts est tenue par Joseph Miller et Andre Nies.

Calcul de fréquencedit

Cette branche de la théorie de la récursivité a analysé la question suivante: Pour m et n fixes avec 0 < m < n, pour quelles fonctions A est-il possible de calculer pour n’importe quelles n entrées différentes x1, x2,…, xn un tuple de n nombres y1, y2, …, yn telles qu’au moins m des équations A(xk ) = yk soient vraies. De tels ensembles sont appelés (m, n) – ensembles récursifs. Le premier résultat majeur de cette branche de la théorie de la récursivité est le résultat de Trakhtenbrot selon lequel un ensemble est calculable s’il est (m, n)-récursif pour certains m, n avec 2m > n. D’autre part, les ensembles semi-directionnels de Jockusch (qui étaient déjà connus de manière informelle avant que Jockusch ne les introduise en 1968) sont des exemples d’un ensemble qui est (m, n)-récursif si et seulement si 2m < n + 1. Il y a un nombre incalculable de ces ensembles et aussi quelques ensembles récursivement énumérables mais non calculables de ce type. Plus tard, Degtev a établi une hiérarchie d’ensembles récursivement énumérables qui sont (1, n + 1) -récursifs mais pas (1, n)-récursifs. Après une longue phase de recherche par des scientifiques russes, ce sujet a été repopularisé en occident par la thèse de Beigel sur les requêtes bornées, qui reliait le calcul de fréquence aux réductibilité bornées susmentionnées et à d’autres notions connexes. L’un des résultats majeurs a été la théorie de la cardinalité de Kummer qui stipule qu’un ensemble A est calculable si et seulement s’il existe un n tel qu’un algorithme énumère pour chaque tuple de n nombres différents jusqu’à n de nombreux choix possibles de la cardinalité de cet ensemble de n nombres recoupés avec A; ces choix doivent contenir la vraie cardinalité mais en omettre au moins une fausse.

Inférence inductivedit

C’est la branche récursive-théorique de la théorie de l’apprentissage. Il est basé sur le modèle d’apprentissage à la limite de E. Mark Gold de 1967 et a développé depuis de plus en plus de modèles d’apprentissage. Le scénario général est le suivant: Étant donné une classe S de fonctions calculables, existe-t-il un apprenant (c’est-à-dire une fonction récursive) qui sort pour toute entrée de la forme (f(0), f(1),…, f(n)) une hypothèse. Un apprenant M apprend une fonction f si presque toutes les hypothèses ont le même indice e de f par rapport à une numérotation acceptable précédemment convenue de toutes les fonctions calculables; M apprend S si M apprend tous les f dans S. Les résultats de base sont que toutes les classes récursivement énumérables de fonctions sont apprenables alors que la classe REC de toutes les fonctions calculables n’est pas apprenable. De nombreux modèles connexes ont été envisagés et l’apprentissage de classes d’ensembles récursivement énumérables à partir de données positives est un sujet étudié à partir de l’article pionnier de Gold en 1967.

Généralisations de la calculabilité de Turingmodifier

La théorie de la récursivité comprend l’étude de notions généralisées de ce domaine telles que la réductibilité arithmétique, la réductibilité hyperarithmétique et la théorie de la récursivité α, comme décrit par Sacks (1990). Ces notions généralisées comprennent des réductibilité qui ne peuvent pas être exécutées par des machines de Turing mais qui sont néanmoins des généralisations naturelles de réductibilité de Turing. Ces études comprennent des approches pour étudier la hiérarchie analytique qui diffère de la hiérarchie arithmétique en permettant la quantification sur des ensembles de nombres naturels en plus de la quantification sur des nombres individuels. Ces domaines sont liés aux théories des ordres de puits et des arbres ; par exemple, l’ensemble de tous les indices d’arbres récursifs (non binaires) sans branches infinies est complet pour le niveau Π 1 1 {\displaystyle\Pi _{1}^{1}}

de la hiérarchie analytique. La réductibilité de Turing et la réductibilité hyperarithmétique sont importantes dans le domaine de la théorie descriptive efficace des ensembles. La notion encore plus générale de degrés de constructibilité est étudiée en théorie des ensembles.

Théorie de calcul continuemodifier

La théorie de calcul pour le calcul numérique est bien développée. La théorie de la calculabilité est moins bien développée pour le calcul analogique qui se produit dans les ordinateurs analogiques, le traitement du signal analogique, l’électronique analogique, les réseaux de neurones et la théorie du contrôle en temps continu, modélisée par des équations différentielles et des systèmes dynamiques continus (Orponen 1997; Moore 1996).