Décider (Turing Machine) – Wikipedia wiki

Machine Turing qui s’arrête pour toute entrée

En théorie de la calculabilité, un décideur est une machine Turing qui s’arrête pour chaque entrée. ^[d’abord] Un décideur est également appelé Machine de Turing totale ^[2] car il représente une fonction totale.

Parce que cela s’arrête toujours, une telle machine est en mesure de décider si une chaîne donnée est membre d’un langage formel. La classe de langues qui peut être décidée par ces machines est l’ensemble des langues récursives.

Compte tenu d’une machine de Turing arbitraire, déterminer s’il s’agit d’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.

Fonctions calculables par des machines totales de Turing [ modifier ]]

En pratique, de nombreuses fonctions d’intérêt sont calculables par des machines qui s’arrêtent toujours. Une machine qui utilise uniquement une mémoire finie sur une entrée particulière peut être forcée de s’arrêter pour chaque entrée en restreignant ses capacités de contrôle de flux afin qu’aucune entrée ne fasse jamais entrer la machine à entrer une boucle infinie. À titre d’exemple trivial, une machine mettant en œuvre un arbre de décision fine s’arrêtera toujours.

Il n’est pas nécessaire que la machine soit entièrement exempte de capacités de boucle, cependant, de garantir l’arrêt. Si nous restreignions les boucles de taille de manière prévisible (comme la boucle FOR dans la base), 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 de jouets pl- {goto} de Brainerd et Landweber (1974).

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

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

Relation avec les machines Turing partielles [ modifier ]]

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

1. Chaque fonction partielle calculable par une machine de Turing partiel peut-elle être étendue (c’est-à-dire, son domaine a-t-il agrandi) pour devenir une fonction totale calculable?
2. Est-il possible de modifier la définition d’une machine Turing afin qu’une classe particulière de machines Turing totales, en 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 des machines qui s’arrêtent toujours n’incluent pas d’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’abandon algorithmique du problème d’arrêt.

En effet, si g une fonction calculable totale s’étendait F alors g serait calculable par une machine Turing; réparer C’est comme l’indice d’une telle machine. Construisez une machine Turing M , en utilisant le théorème de la récursivité de Kleene, qui en entrée 0 simule la machine avec l’index C’est exécuter sur un index n _M pour M (Ainsi la machine M peut produire un indice de lui-même; C’est le rôle du théorème de la récursivité). Par hypothèse, cette simulation reviendra éventuellement une réponse. Définir M ^{[ clarifier ]]} pour que si g ( n _M ) = m puis la valeur de retour de M est

${displaystyle m + 1}$

. Ainsi F ( n _M ), la vraie valeur de retour de M en entrée 0 , n’égalera pas g ( n _M ). Ainsi g ne s’étend pas F .

La deuxième question demande, en substance, s’il existe un autre modèle de calcul raisonnable qui ne calcule que les fonctions totales et calcule toutes les fonctions calculables totales. De manière informelle, si un tel modèle existait, chacun de ses ordinateurs pourrait être simulé par une machine Turing. Ainsi, si ce nouveau modèle de calcul consistait en une séquence

${displayStyle m_ {1}, m_ {2}, ldots}$

des machines, il y aurait une séquence récursivement énumérable

${displayStyle t_ {1}, ldots t_ {2}, ldots}$

de machines Turing qui calculent les fonctions totales et que chaque fonction totale calculable soit calculable par l’une des machines T _je . C’est impossible, car une machine T pourrait être construit de telle sorte que sur l’entrée je la machine T Retour

${displayStyle t_ {i} (i) +1,}$

. Cette machine ne peut être équivalente à aucune machine T sur la liste: supposons que ce soit sur la liste de l’index J . Alors

${displaystyle T_{j}(j)=T_{j}(j)+1,}$

, qui ne renvoie pas de résultat entier. Par conséquent, il ne peut pas être total, mais la fonction par construction doit être totale (si les fonctions totales sont énumérables récursivement, alors cette fonction peut être construite), ce qui est une contradiction. Cela montre que la deuxième question a une réponse négative.

L’ensemble des indices des machines de Turing total [ modifier ]]

Le problème de décision de savoir si la machine Turing avec index C’est L’arrêt sur chaque entrée n’est pas décidable. En fait, ce problème est au niveau

${displayStyle pi _ {2} ^ {0}}$

de la hiérarchie arithmétique. Ainsi, ce problème est strictement plus difficile que le problème d’arrêt, qui demande si la machine avec index C’est s’arrête sur l’entrée 0 . Intuitivement, cette différence de non-solvabilité est due au fait que chaque instance du problème de la “machine totale” représente l’infini de nombreuses instances du problème d’arrêt.

Provabilité [ modifier ]]

On peut être intéressé non seulement par la question de savoir si une machine Turing est totale, mais aussi pour savoir si cela peut être prouvé dans un certain système logique, comme l’arithmétique de Premier Ordre.

Dans un système d’épreuve sonore, chaque machine de Turing prouvable totale est en effet totale, mais l’inverse n’est pas vrai: de manière informelle, pour chaque système d’épreuve de premier ordre qui est suffisamment fort (y compris l’arithmétique d’arano), il existe des machines Turing qui sont supposées être total, mais ne peut être prouvé en tant que tel, sauf si le système est incohérent (auquel cas on peut prouver n’importe quoi). La preuve de leur totalité repose sur certaines hypothèses ou nécessite 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 Turing sur l’entrée n qui passe par les n preuves n et rechercher une contradiction. S’il en trouve un, il entre dans une boucle infinie et ne s’arrête jamais; Sinon, cela s’arrête. Si le système est cohérent, la machine Turing s’arrête sur chaque entrée, mais on ne peut pas le prouver dans un système de preuve suffisamment fort en raison des théorèmes d’incomplétude de Gödel.

On peut également créer une machine Turing qui s’arrête 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 Turing qui, quelle que soit l’entrée, énumère toutes les preuves et s’arrête sur une contradiction.

Une machine Turing qui passe par des séquences de Goodstein et s’arrête à zéro est totale mais ne peut pas être prouvée comme telle dans l’arithmétique d’arano.

Voir également [ modifier ]]

Les références [ modifier ]]

• Brainerd, W.S., Landweber, L.H. (1974), Théorie du calcul , Wiley.
• Meyer, A.R., Ritchie, D.M. (1967), La complexité des programmes de boucle , Proc. des réunions nationales de l’ACM, 465.
• Sipser, M. (2006), Introduction à la théorie du calcul , PWS Publishing Co.
• Choisi, D.C. (1997), Automates et calculabilité , Springer.
• Ohlebusch, E. (2002), Sujets avancés dans la réécriture du terme , Springer.