Les machines de Turing à bande unique avec entrée protégée en écriture reconnaissent uniquement les langues régulières

introduction

Je pensais qu'il pourrait y avoir une erreur dans l'énoncé original de la question, et le PO n'était plus là pour demander. J'ai donc supposé que la bande était en lecture seule partout, et j'ai écrit une première preuve basée sur cette hypothèse, motivée par le fait que le TM a le plein pouvoir de Turing en dehors de la partie d'entrée de la bande s'il peut l'écrire, ce qui induit le faux croyance qu'il peut reconnaître n'importe quel langage RE.

Cependant, ce n'est pas le cas: la restriction à l'écriture sur la partie d'entrée de la bande implique que seules des informations finies peuvent être extraites de l'entrée, limitées par le nombre d'états à l'entrée et à la sortie de cette partie de la bande (combinée avec côté entrée et sortie). InstrutedA doit être crédité pour avoir remarqué dans un commentaire qu'il y a un problème avec la reconnaissance d'une langue RE, car il n'est pas possible de faire une copie de l'entrée sans JAMAIS écrire dans la zone de saisie d'origine,

Par conséquent, j'ai écrit une deuxième preuve qui suppose que seule la section d'entrée de la bande est en lecture seule, le reste étant autorisé en lecture-écriture.

Je garde les deux preuves ici, car la première m'a aidé à trouver la solution, même s'il n'est pas nécessaire de comprendre la deuxième preuve, est plus complexe et est subsumée par la deuxième preuve. Il peut être ignoré. Cependant, la preuve la plus faible a l'avantage d'être constructive (pour obtenir un FSA équivalent à la machine de Turing), tandis que le résultat plus général n'est pas constructif.

Cependant, je donne d'abord le dernier et plus puissant résultat. Je suis un peu surpris de ne pas avoir pu trouver ce résultat, même sans preuve, ailleurs sur le net, ou en demandant à des utilisateurs compétents, et toute référence à des travaux publiés serait la bienvenue.

Contenu:

Les machines de Turing qui n'écrasent pas l'entrée n'acceptent que les langues normales. Cette preuve n'est pas constructive.
Les machines Turing avec des bandes en lecture seule n'acceptent que les langues normales. Il peut être ignoré comme subsumé par la preuve précédente, mais il utilise une approche différente, qui a l'avantage d'être constructive.

Les machines de Turing qui n'écrasent pas l'entrée n'acceptent que les langues normales

Nous rappelons que, si la TM ne remplace pas son entrée, et est donc en lecture seule sur son entrée, la TM peut lire et écrire sur le reste de la bande . La preuve repose sur le fait que le comportement d'observation de la MT sur une entrée inconnue ne peut produire qu'un nombre fini de cas différents. Par conséquent, bien que le TM ait le plein pouvoir de Turing simplement en s'appuyant sur le reste de sa bande, ses informations sur l'entrée, qui peut être n'importe quelle chaîne dans , sont finies, donc il ne peut calculer que sur un nombre fini de différents cas. Cela donne une vision différente du caractère fini des langages réguliers, comportementaux plutôt que structurels. $\Sigma^*$

Nous supposons que la MT accepte lorsqu'elle entre dans un état d'acceptation.

Preuve.

Nous définissons un calcul restreint en entrée (IRC) comme un calcul ( en lecture seule) de la MT de telle sorte que la tête de TM reste sur la partie d'entrée de la bande, sauf éventuellement pour la dernière transition qui peut la déplacer vers une cellule immédiatement au à gauche ou à droite de la zone de saisie.

Un calcul restreint en entrée gauche est un IRC qui démarre sur le symbole le plus à gauche de l'entrée. Un calcul restreint à l'entrée droite est un IRC qui commence sur le symbole le plus à droite de l'entrée.

Nous prouvons d'abord que, pour les calculs restreints en entrée gauche qui commencent dans l'état , les langages suivants sont réguliers: $p$

le langage de chaînes d'entrée tel qu'il y ait un calcul restreint d'entrée gauche, commençant dans l'état , qui se termine sur la première cellule à gauche du symbole d'entrée le plus à gauche dans l'état ; $K_{Lp\to Lq}$ $p$ $q$
le langage de chaînes d'entrée tel qu'il existe un calcul restreint d'entrée gauche, commençant dans l'état , qui se termine sur la première cellule à droite du symbole d'entrée le plus à droite dans l'état ; $K_{Lp\to Rq}$ $p$ $q$
le langage de chaînes d'entrée tel qu'il existe un calcul restreint d'entrée gauche, commençant à l'état , qui atteint un état accepté. $A_{Lp}$ $p$

De même, pour les calculs restreints à l'entrée droite commençant à l'état , les langages définis de manière similaire suivants sont réguliers: , et . $p$ $K_{Rp\to Lq}$ $K_{Rp\to Rq}$ $A_{Rp}$

Les 6 preuves reposent sur le fait que les automates à états finis non déterministes bidirectionnels (2NFA) reconnaissent les ensembles réguliers (voir Hopcroft + Ullman 1979, pp 36-41, et exécutent 2.18 page 51). Un 2NFA fonctionne comme une MT en lecture seule sur une bande limitée à son entrée, en commençant initialement par le symbole le plus à gauche, et en acceptant en se déplaçant au-delà de l'extrémité droite dans un état d'acceptation.

Dans chacun des 6 cas, la preuve est faite en construisant un 2NFA qui imite les calculs restreints en entrée, mais avec quelques transitions supplémentaires pour s'assurer qu'il peut commencer à partir de la cellule la plus à gauche et accepter la langue en quittant l'extrémité la plus à droite dans une acceptation Etat. Pour les langues , l'état d'acceptation d'origine de la MT est changé en états conduisant à un arrêt du calcul non acceptant. Dans deux cas, il peut être nécessaire d'ajouter une cellule supplémentaire avec un nouveau symbole de garde à gauche pour détecter les calculs TM qui se termineraient à l'extrémité gauche, afin de les faire se terminer à l'extrémité droite. $K_{??\to ??}$

Ces langages sont définis pour toutes les combinaisons d'états et de la machine de Turing d'origine. Ils représentent tout ce qui peut être observé (donc connu et calculé) de l'entrée par la MT. $p$ $q$

Si est le nombre d'états, on définit donc langues et langues , soit un total de langues. En fait, certaines de ces langues peuvent être égales. $k$ $4k^2$ $K_{??\to ??}$ $2k$ $A_{??}$ $4k^2+2k$

Ce sont les seuls calculs restreints en entrée possibles de la MT commençant à une extrémité de l'entrée. Par conséquent, les calculs induits par chaque chaîne d'entrée (en dehors de la section d'entrée de la bande) sont caractérisés par l'ensemble de ces langues auxquelles l'entrée appartient ou n'appartient pas, donc par une intersection de chacune de ces langues ou de ses complément dans . Toutes ces intersections sont des intersections finies de r langues régulières, ou leur complément qui sont également réguliers, et sont donc réguliers. $4k^2+2k$ $\Sigma^*$ $4k^2+2k$

Par conséquent, l'ensemble de ces intersections définit une partition de dans au plus langues régulières ( au plus parce que certaines langues initiales peuvent être égales, et certaines intersections peuvent être aussi). Toutes les chaînes appartenant à la même classe d'équivalence peuvent produire exactement le même comportement, comme vu depuis les extrémités de l'entrée. Cela implique qu'ils ne peuvent pas être distingués pour le calcul de la machine de Turing, si vous résumez ce qui se passe dans la zone d'entrée en lecture seule. $\mathcal P$ $\Sigma^*$ $2^{4k^2+2k}$

Si nous prenons deux chaînes et dans la même classe d'équivalence de , nous pouvons prouver, par récurrence sur le nombre de fois que la zone d'entrée est entrée, que pour tout calcul acceptant de la MT sur , il y a une acceptation Calcul TM sur qui est identique partout en dehors de la zone d'entrée. Par conséquent, soit toutes les chaînes d'une classe d'équivalence sont acceptées, soit aucune ne l'est. En conséquence, la langue acceptée par le TM est une union des classes d'équivalence de . C'est donc une union finie de langues régulières, et donc c'est une langue régulière. $u$ $v$ $\mathcal P$ $u$ $v$ $\mathcal P$

Pour être très complet, nous avons ignoré le cas de la chaîne d'entrée vide. Dans ce cas, nous avons juste une MT normale, qui peut lire ou écrire n'importe où. S'il atteint un état acceptant, la chaîne vide est dans la langue, sinon elle ne l'est pas. Mais cela a peu d'effet sur le fait que la langue reconnue est régulière.

Bien sûr, il n'est pas possible de décider si une classe d'équivalence est ou non dans le langage (il en va de même pour la chaîne vide). Ceci est une preuve non constructive.

QED

Les machines Turing avec des bandes en lecture seule n'acceptent que les langues normales

Ceci est subsumé par le résultat précédent. Il est conservé car il utilise une approche différente, probablement moins élégante, et m'a aidé à trouver la preuve précédente en comprenant ce qui compte. Mais il peut très bien être ignoré par les lecteurs. Cependant, un avantage de cette preuve est qu'il s'agit d'une preuve constructive produisant une FSA acceptant la langue. Hendrik Jan donne une esquisse d'une preuve similaire dans sa réponse à une question similaire précédente , qui suppose que la bande entière était en lecture seule.

Je suppose que le symbole vierge qui se trouve sur la partie inutilisée de la bande ne fait jamais partie de l'entrée. Ce symbole est noté ici . La MT est censée accepter lorsqu'elle atteint un état acceptant. $\Box$

La première étape de la preuve consiste à montrer que la tête n'a jamais besoin de quitter la zone d'entrée de la bande. Nous analysons ainsi ce qui se passe lorsque la tête s'écarte du symbole d'entrée le plus à droite. L'analyse lors du déplacement de l'extrême gauche est identique.

Si l'on considère que la tête s'est déplacée sur la première cellule vide à droite de l'entrée, la MT étant dans l'état , il faut comprendre ce qui peut arriver. Il y a en fait trois cas, qui peuvent être simultanément possibles lorsque la MT n'est pas déterministe: $q$

la TM continue à calculer pour toujours, sans que la tête ne revienne jamais sur la partie d'entrée de la bande;
la MT atteint un (a) acceptant ou (b) s'arrête dans un état non acceptant;
la tête TM revient finalement sur la cellule la plus à droite de l'entrée, le contrôle fini étant dans l'état . $r$

Nous devons donc analyser le comportement du contrôle TM fini, lors du calcul sur une demi-bande vierge, en commençant dans l'état sur la cellule la plus à gauche d'une demi-bande vierge, infini vers la droite. $q$

Étant donné que la MT n'écrit pas et ne lit que le symbole vide , tout le contrôle fini peut faire est de se déplacer vers la gauche ou vers la droite, et les configurations ne sont différenciées que par la position de la tête, c'est-à-dire par un entier. La bande peut être remplacée par un compteur, à partir de , qui est incrémenté lorsque la tête se déplace vers la droite et décrémenté lorsqu'elle se déplace vers la gauche, à condition de ne considérer que les transitions qui nécessitent le symbole vierge sur la bande. Si le compteur descend à , cela correspond à un cas où la tête revient sur le symbole d'entrée le plus à droite. $\Box$ $1$ $0$

Une première remarque est que nous pouvons ignorer les calculs qui ne se terminent pas (cas 1) ou qui se terminent par rejet (cas 2.b) car la terminaison avec acceptation est le seul cas pertinent pour accepter une chaîne. Nous voulons donc seulement savoir si le compteur peut descendre à , et dans quel état, ou si le calcul peut atteindre un état acceptant. $0$

Nous représentons la partie pertinente du contrôle des états finis par un graphe orienté où les sommets sont les états de la MT, et où les arêtes sont les transitions vides, avec un poids +1 ou -1 selon que la tête est supposée bouger droite ou gauche.

Nous définissons l'ensemble de l'état partir duquel un état accepteur peut être atteint avec un chemin pondéré positif. $A_R$ $q$

Nous calculons également l'ensemble de toutes les paires d'états de telle sorte qu'il existe un chemin de poids de à , mais aucun préfixe de ce chemin n'a un poids négatif. $E_R$ $(q,r)$ $-1$ $q$ $r$

Ensuite, nous modifions le contrôle d'état fini de la MT comme suit (en ignorant maintenant toutes les transitions sur le symbole vide ): $\Box$

Nous créons un nouvel état acceptant sans transition. $q_A$

Pour chaque transition vous ajoutez une transition si (c'est-à-dire qu'une acceptation est possible si vous êtes sur le symbole le plus à droite). $p,a\mapsto R,q$ $p,a\mapsto R,q_A$ $q\in A_R$

Pour chaque transition et chaque paire vous ajoutez une transition factice , où indique que la tête ne doit pas bouger. Comme ce n'est pas un mouvement autorisé avec la plupart des formalisations d'automates, ces états fictifs peuvent être éliminés par la fermeture transitive par la suite. $p,a\mapsto R,q$ $(q,r)\in E_R$ $p,a\mapsto S,r$ $S$

Une fois cette opération terminée, nous procédons à la suppression des transitions factices. Pour chaque symbole de bande , nous construisons l'ensemble , et nous considérons la fermeture transitive de la relation définie par . Ensuite, pour chaque transition de la TM d'origine, et pour chaque paire , nous ajoutons une nouvelle transition . Ensuite, toutes les transitions factices peuvent être supprimées. $a$ $F_a=\{(p,r)\mid \text{ there is a dummy transition } p,a\mapsto S,r\}$ $F_a^*$ $F_a$ $r,a\mapsto L,s$ $(p,r)\in F_a^*$ $p,a\mapsto L,s$

Nous procédons de la même manière pour les mouvements de la tête à gauche de la partie d'entrée de la bande, inversant ainsi à gauche et à droite, et échangeant et dans les poids du graphe. $+1$ $-1$

Une fois cela fait, nous supprimons complètement toutes les transitions sur les cellules vides, car le calcul correspondant est court-circuité par les nouvelles transitions. Et nous avons maintenant un nouveau TM avec une tête qui reste sur l'entrée tout le temps, sauf lors de l'acceptation avec l'état , et reconnaît toujours la langue d'origine. $q_A$

Nous devons maintenant faire quelques changements cosmétiques, afin que cette MT se comporte exactement comme un NDA bidirectionnel (l'acceptation ne se fait qu'en quittant l'entrée de droite dans un état d'extinction). On peut alors s'appuyer sur l'équivalence connue entre 2-NDA et FSA (voir par exemple Hopcroft + Ullman 1979, page 40) pour obtenir la preuve que le langage est régulier.

QED

babou
la source

Les machines de Turing à bande unique avec entrée protégée en écriture reconnaissent uniquement les langues régulières

Réponses:

introduction

Les machines de Turing qui n'écrasent pas l'entrée n'acceptent que les langues normales

Les machines Turing avec des bandes en lecture seule n'acceptent que les langues normales