Les restrictions de Turing Machine qui rendent l’arrêt décidable

Si on restreint Turing Machines à une bande finie (c'est-à-dire d'utiliser un espace délimité ), le problème d'arrêt est décidable, essentiellement parce qu'après plusieurs étapes (pouvant être calculées à partir du nombre d'états Q , S et taille de l'alphabet), une configuration doit être répétée.$S$$Q$$S$

Existe-t-il d'autres restrictions naturelles à la machine de Turing qui rendent la décision décisive?

Bien sûr, si le graphe de transition d’état n’a pas de boucles ni de cycles, l’arrêt est décidable. D'autres?

Une variante assez naturelle et étudiée est la machine de Turing à inversion de bande (le nombre d'inversions de bande est limité); voir par exemple:

Juris Hartmanis: Calculs de la machine de Turing bornée par inversion de bande. J. Comput. Syst. Sci. 2 (2): 117-135 (1968)

Edit : [cette variante est plus artificielle] le problème d’arrêt est décidable pour une machine de Turing non-effaçante ayant au plus deux instructions gauches sur l’alphabet ; voir Maurice Margenstern: Les machines de Turing non effaçantes: une frontière entre un problème décisif décisif et l’universalité. Théor Comput. Sci. 129 (2): 419-424 (1994)$\{0,1\}$

Considérant que la transmission des paramètres aux sous-routines et une grande partie de la gestion de la mémoire dans les langages informatiques courants est basée sur la pile, une variante évidente et naturelle consiste à limiter la mémoire non limitée d'une machine de Turing à une pile.

Un tel modèle a de bonnes propriétés , en plus d’arrêter de pouvoir être décidé (bien connu pour les PDA ):

La notion d'un PDA peut être généralisé à un auxiliaire automate à pile ( S ( n ) -AuxPDA)$S(n)$$S(n)$ . Cela consiste en

1. une bande d'entrée en lecture seule, entourée de marqueurs de fin,
2. un contrôle d'état fini,
3. une bande de stockage en lecture-écriture de longueur , où n est la longueur de la chaîne d'entrée, et$S(n)$$n$
4. une pile

Dans "Hopcroft / Ullman (1979) Introduction à la théorie des automates, aux langages et au calcul (1re éd.), Nous trouvons:

Théorème 14.1 Ce qui suit est équivalent à .$S(n)\geq\log n$

1. est accepté par un déterministe S ( n ) -AuxPDA$L$$S(n)$
2. est accepté par un non déterministe S ( n ) -AuxPDA$L$$S(n)$
3. est en DTIME ( c S ( n ) ) pour une constante c .$L$$\operatorname{DTIME}(c^{S(n)})$$c$

avec l'étonnant:

Le corollaire est dans P si et seulement si L est accepté par un log n -AuxPDA.$L$$\mathsf P$$L$$\log n$

le libellé de cette question est légèrement problématique, car une machine de Turing avec un ruban fini est sans doute relativement peu liée à une machine de Turing et plus proche d’une machine à états finis. De même avec toutes les autres "restrictions" sur les machines de Turing, presque toutes les restrictions semblent constituer un phénomène totalement différent (c'est-à-dire autre que la complétude de Turing avec des propriétés complètement différentes). en fait, certains articles décrivent / étudient maintenant cette limite en détail, ce qui peut présenter une similitude approximative avec une autre limite informatique connue, à savoir les transitions de phase complètes NP.

et il est quelque peu contre-intuitif de penser que la théorie des FSM "plus simple au point de vue du calcul / entièrement décidable" est apparue longtemps après l'invention de la machine de Turing, vraisemblablement inspirée par celle-ci. alors peut-être une façon de la reformuler est de demander les "modèles décidables les plus sophistiqués" ou "l'étude de la frontière entre les modèles informatiques indécidables et décidables".

de toute façon, légèrement reformulé de cette façon, une solution raisonnable / théorie / programme de recherche non encore répertoriée est la théorie des automates chronométrés actuellement développée de manière significative et activement recherchée / en cours qui vient de remporter un prix de l’Église pour Alur / Dill. Voici un exemple d’article sur les automates temporisés et l’étude de la limite de décidabilité du modèle de calcul, et il en existe beaucoup d’autres.

• Résultats de décidabilité et de complexité pour les automates temporisés via des machines à canaux / Abdulla, Deneux, Worrell

• Prix ​​2016 de l'église Alonzo, Automates temporisés, Alur / Dill

• Une théorie des automates temporisés / Alur, Dill

• Entretien avec Rajeev Alur et David Dill, récipiendaires du prix Alonzo Church Award 2016 / Aceto, Journal Algèbre de processus