Décideur (machine de Turing)

En théorie de la calculabilité , un décideur est une machine de Turing qui s'arrête à chaque entrée. Un décideur est également appelé machine de Turing totale car il représente une fonction totale .

Comme elle s'arrête toujours, une telle machine est capable de décider si une chaîne donnée appartient à un langage formel . La classe de langages qui peuvent être décidés par de telles machines est l'ensemble des langages récursifs .

Étant donnée une machine de Turing arbitraire, déterminer si elle est un décideur est un problème indécidable . Il s'agit d'une variante du problème d'arrêt , qui demande si une machine de Turing s'arrête sur une entrée spécifique.

En pratique, de nombreuses fonctions intéressantes sont calculables par des machines qui s'arrêtent toujours. Une machine qui n'utilise qu'une mémoire finie sur une entrée particulière peut être forcée de s'arrêter pour chaque entrée en limitant ses capacités de contrôle de flux de sorte qu'aucune entrée ne fasse jamais entrer la machine dans une boucle infinie . À titre d'exemple trivial, une machine implémentant un arbre de décision finitaire s'arrêtera toujours.

Il n'est cependant pas nécessaire que la machine soit entièrement dépourvue de capacités de bouclage pour garantir l'arrêt. Si nous limitons les boucles à une taille finie prévisible (comme la boucle FOR en BASIC ), nous pouvons exprimer toutes les fonctions récursives primitives (Meyer et Ritchie, 1967). Un exemple d'une telle machine est fourni par le langage de programmation jouet PL-{GOTO} de Brainerd et Landweber (1974).

Nous pouvons définir un langage de programmation dans lequel nous pouvons garantir que même les fonctions les plus sophistiquées s'arrêtent toujours. Par exemple, la fonction d'Ackermann , qui n'est pas récursive primitive, est néanmoins une fonction calculable totale calculable par un système de réécriture de termes avec un ordre de réduction sur ses arguments (Ohlebusch, 2002, pp. 67).

Malgré les exemples ci-dessus de langages de programmation qui garantissent l'arrêt des programmes, il n'existe aucun langage de programmation qui capture exactement la totalité des fonctions récursives , c'est-à-dire les fonctions qui peuvent être calculées par une machine de Turing qui s'arrête toujours. En effet, l'existence d'un tel langage de programmation serait en contradiction avec la non-semi-décidabilité du problème de savoir si une machine de Turing s'arrête à chaque entrée.

Une machine de Turing générale calculera une fonction partielle. Deux questions peuvent être posées sur la relation entre les machines de Turing partielles et les machines de Turing totales :

1. Toute fonction partielle calculable par une machine de Turing partielle peut-elle être étendue (c’est-à-dire voir son domaine élargi) pour devenir une fonction calculable totale ?
2. Est-il possible de modifier la définition d'une machine de Turing afin qu'une classe particulière de machines de Turing totales, calculant toutes les fonctions calculables totales, puisse être trouvée ?

La réponse à chacune de ces questions est non.

Le théorème suivant montre que les fonctions calculables par les machines qui s'arrêtent toujours n'incluent pas les extensions de toutes les fonctions calculables partielles, ce qui implique que la première question ci-dessus a une réponse négative. Ce fait est étroitement lié à l'insolvabilité algorithmique du problème d'arrêt .

En effet, si g était une fonction calculable totale étendant f alors g serait calculable par une machine de Turing ; fixez e comme indice d'une telle machine. Construisez une machine de Turing M , en utilisant le théorème de récursivité de Kleene , qui en entrée0 simule la machine d'indice e fonctionnant sur un indice n _M pour M (donc la machine M peut produire un indice d'elle-même ; c'est le rôle du théorème de récursivité). Par hypothèse, cette simulation finira par renvoyer une réponse. Définissons M de telle sorte que si g ( n _M ) = m alors la valeur de retour de M soit ⁠ ⁠ . Ainsi f ( n _M ), la vraie valeur de retour de M en entrée0 , ne sera pas égal à g ( n _M ). Par conséquent, g ne prolonge pas f .

La deuxième question demande, en substance, s'il existe un autre modèle raisonnable de calcul qui ne calcule que les fonctions totales et calcule toutes les fonctions totales calculables. De manière informelle, si un tel modèle existait, chacun de ses ordinateurs pourrait être simulé par une machine de Turing. Ainsi, si ce nouveau modèle de calcul consistait en une séquence de machines, il y aurait une séquence récursivement énumérable de machines de Turing qui calculent des fonctions totales et de sorte que chaque fonction totale calculable soit calculable par l'une des machines T _i . Cela est impossible, car une machine T pourrait être construite de telle sorte qu'à l'entrée i la machine T renvoie . Cette machine ne peut être équivalente à aucune machine T de la liste : supposons qu'elle soit sur la liste à l'index j . Alors , qui ne renvoie pas un résultat entier. Par conséquent, elle ne peut pas être totale, mais la fonction par construction doit être totale (si les fonctions totales sont récursivement énumérables, alors cette fonction peut être construite), ce qui est une contradiction. Cela montre que la deuxième question a une réponse négative.

Le problème de décision de savoir si la machine de Turing d'indice e s'arrêtera à chaque entrée n'est pas décidable. En fait, ce problème se situe au niveau de la hiérarchie arithmétique . Ce problème est donc strictement plus difficile que le problème d'arrêt , qui demande si la machine d'indice e s'arrête à l'entrée 0. Intuitivement, cette différence d'insolvabilité est due au fait que chaque instance du problème de la « machine totale » représente une infinité d'instances du problème d'arrêt.

On peut s'intéresser non seulement à savoir si une machine de Turing est totale, mais aussi à savoir si cela peut être prouvé dans un certain système logique, comme l'arithmétique de Peano du premier ordre .

Dans un système solide , toute machine de Turing prouvable comme totale est effectivement totale, mais la réciproque n'est pas vraie : de manière informelle, pour tout système de preuve du premier ordre suffisamment solide (y compris l'arithmétique de Peano), il existe des machines de Turing qui sont supposées totales, mais qui ne peuvent être prouvées comme telles, à moins que le système ne soit incohérent (auquel cas on peut tout prouver). La preuve de leur totalité repose soit sur certaines hypothèses, soit sur un autre système de preuve.

Ainsi, comme on peut énumérer toutes les preuves du système de preuve, on peut construire une machine de Turing sur l'entrée n qui parcourt les n premières preuves et cherche une contradiction. Si elle en trouve une, elle entre dans une boucle infinie et ne s'arrête jamais ; sinon, elle s'arrête. Si le système est cohérent , la machine de Turing s'arrêtera à chaque entrée, mais on ne peut pas le prouver dans un système de preuve suffisamment solide en raison des théorèmes d'incomplétude de Gödel .

On peut aussi créer une machine de Turing qui s'arrêtera si et seulement si le système de preuve est incohérent, et est donc non total pour un système cohérent mais ne peut pas être prouvé tel : Il s'agit d'une machine de Turing qui, quelle que soit l'entrée, énumère toutes les preuves et s'arrête sur une contradiction.

Une machine de Turing qui parcourt les séquences de Goodstein et s'arrête à zéro est totale mais ne peut pas être prouvée comme telle en arithmétique de Peano.