J'ai vu des machines de turing être représentées avec des bandes infinies dans une et dans deux directions. Y a-t-il une différence dans la puissance de ces machines de turing, ou sont-elles fondamentalement équivalentes? Dans ma tête, je pense qu'ils sont équivalents, car je suppose qu'il doit y avoir un moyen de représenter la bande infinie bidirectionnelle comme une bande infinie unidirectionnelle, mais je n'arrive pas à trouver une preuve ou un exemple.
turing-machines
user2795095
la source
la source
Réponses:
Ils sont équivalents en puissance de calcul. Tout ce qui est calculable par l'un de ces deux types de machines de Turing, est calculable par l'autre type. Voyons comment simuler une machine de Turing avec une bande doublement infinie, sur une machine de Turing avec une bande singulièrement infinie.
L'idée est de couper votre bande doublement infinie en deux, de sorte que vous ayez deux bandes infiniment simples, une gauche et une droite, que vous fusionnerez finalement. Vous pouvez marquer les extrémités avec un emplacement de bande contenant un symbole EOF spécial. Vous dupliquez également votre contrôle fini, de sorte que vous disposez de deux contrôles d'état fini identiques. Vous supposez que vous avez un périphérique de passage de contrôle (voir ci-dessous), de sorte que, lorsque la machine de gauche essaie d'aller au-delà de l'extrémité droite de sa bande, elle passe le contrôle à la machine de droite, sur sa position de bande la plus à gauche (juste avant le extrémité gauche de la bande de droite). Et inversement, en essayant de passer l'extrémité gauche de la bande droite.
Nous sommes maintenant prêts à fusionner les deux demi-bandes, par exemple en repliant la droite sur la gauche. Pour cela, vous retournez la moitié droite de la bande et vous veillez à modifier en conséquence les transitions, en échangeant de droite à gauche et de gauche à droite. Ensuite, vous fusionnez les deux demi-bandes en une seule bande contenant des paires de symboles, un gauche et un droit, chaque composant étant éventuellement vierge.
Vous modifiez à nouveau les transitions des deux machines, de sorte que les transitions gauche (resp. Droite) utilisent et modifient uniquement les parties gauche (resp. Droite) des paires sur la bande. Ensuite, vous fusionnez le contrôle des deux machines par simple union set respectivement pour les états et pour les transitions.
Vous ajoutez un ensemble de transitions pour chaque état existant, de sorte que lorsque le symbole de bande est EOF, il retourne à l'emplacement de bande précédent (le premier emplacement non EOF) et l'état change à son homologue chiral: s'il s'agit d'une gauche (resp. à droite), il change à son homologue droit (resp. à gauche). C'est le dispositif de passage de contrôle.
J'ai peut-être oublié un détail, mais c'est l'idée générale de la construction. La preuve est laissée en exécution.
Bien sûr, la bande initiale (entrée) doit être modifiée en conséquence. Mais cela peut être rendu simple en plaçant l'entrée (si elle est finie) complètement sur le côté gauche (celle qui n'est pas retournée) de la bande coupée.
Ensuite, vous rangez le tournevis car cela peut être dangereux pour les enfants.
PS J'ai seulement montré que la bande doublement infinie peut être simulée avec une bande singulièrement infinie. L'inverse semble trop évident.
la source