Les machines sont-Turing plus puissants que les automates à pile?

Question

Je suis venu avec un résultat en lisant quelques livres d'automates, que les machines de Turing semblent être plus puissants que les automates à pile. Etant donné que la bande d'une machine de Turing peut toujours être à se comporter comme une pile, il avait l'air que nous pouvons affirmer en fait que plus puissants sont les mémoires de traduction.

Est-ce vrai?

Answer 1

Si l'on considère seulement que « les machines de Turing peuvent toujours être faits pour se comporter comme une pile », vous pouvez seulement conclure qu'ils sont au moins aussi puissant que pushdown automates.

Mais en général, oui, il est vrai, les machines de Turing sont plus puissants que les PDA. L'exemple le plus simple serait de montrer que les machines de Turing peuvent décrire les langues contexte sensibles.

Answer 2

Vous ne pouvez pas aller au fond de la pile sans « oublier » le reste de la pile. Avec une machine de Turing, vous pouvez facilement revenir en arrière sur la bande.

Cette simple tâche ne peut pas être fait avec un transducteur pushdown (à peu près la même chose que les automates pushdown, mais peut écrire des choses à chaque étape), mais peut facilement être fait avec une bande:

  

Lire une chaîne $ w $, puis écrire la chaîne deux fois: $ $ ww

Si vous ne voulez pas entendre parler de transducteurs, le même problème est pour vous: cette langue est facilement reconnaissable par une machine de Turing, mais pas avec un automate pushdown:

$$ = L \ {ww \ mid w \ dans S ^ * \} $$

mais je pense qu'avec un transducteur vous obtenez une bonne compréhension de la différence.

Answer 3

sont en effet des machines de Turing plus puissants que les PDA réguliers.

Cependant, dans le cas particulier d'un PDA avec deux piles (TPDA ou 2-PDA) le TPDA est tout aussi puissant qu'un automate turation.

L'idée de base est que vous pouvez simuler la bande du TM en utilisant deux piles: dans le tout pile gauche est stockée qui est à gauche de la tête sur le Turing-bande, tandis que le symbole sous la tête et tout droit de la tête est stocké dans l'autre pile. Et ainsi le TPDA peut simuler le travail d'une machine de Turing, et ils sont équivalents. Vous trouverez une description un peu plus détaillée .

Answer 4

Une machine de Turing est plus puissant que un pushdown automate - qui est un théorème fondamental de la théorie des automates et peut être prouvée de plusieurs façons. Par exemple, le problème de l'arrêt est indécidable pour les mémoires de traduction - il n'y a pas de programme (ou autre TM) qui sera toujours donner un bon oui ou pas de réponse à la question: sera ce TM sur cet arrêt d'entrée. Mais pour les PDA, le problème de l'arrêt est résoluble. Ainsi, les modèles ont un pouvoir intrinsèquement différents, le modèle TM a plus de puissance que le modèle PDA, mais aussi « souffre » pour elle.

deux pushdown automates "travailler ensemble" peut simuler une machine de Turing. Nous devons simplement préciser ce que nous entendons par deux assistants numériques personnels travaillant ensemble - ils sont tous deux connectés à la chaîne d'entrée et chacun peut travailler avec sa pile indépendamment de l'autre. Leurs contrôles d'états finis sont également connectés, ou équivalent, fusionnés en un seul contrôle état fini.

La preuve qui va à peu près que chacun des PDA peut simuler la moitié de la bande du TM, qui est, la partie des mémoires de traduction bande à partir de la place de la maison et aller indéfiniment à gauche ou à droite. Les détails peuvent être un peu brouillon, mais l'idée de base est simple. La partie supérieure de la « gauche » magasin pushdown représente le carré de tête actuel de la TM et le fond représente le carré de gauche active de la bande du TM; De même pour le magasin pushdown « droit ». Comme pour les déplacements, par exemple, lorsque le TM se déplace d'une case à gauche, le combo simulant des PDA POPS un symbole de la boutique droite pushdown et il pousse sur le dessus du magasin pushdown gauche. Lorsque le TM réécrit le symbole sous sa tête, la gauche apparaît pda son symbole supérieur (la valeur avant) et un autre symbole REPOUSSE (la nouvelle valeur).

Ainsi, le combo de deux PDA travailler de cette façon a exactement la même puissance que les mémoires de traduction, et le problème de l'arrêt du combo est indécidable.

Answer 5

Juste présentent un TM accepter $ 0 ^ n ^ 1 n 2 ^ n $, ce qui contexte isnt't libre (et donc il n'y a pas de PDA il acceptent).

Answer 6

La preuve habituelle est un avec détour.

1. Montrer que pushdown-automates acceptent exactement le langues hors-contexte , l'ensemble des langues acceptées par grammaires contexte. (Dans un livre de texte sur la question)
2. Notez que les machines de Turing acceptent toutes les langues récursifs (par définition).
3. Montrer que les langues sans contexte sont un sous-ensemble des langues récursives, par exemple via pompage Lemme - - qui est facilement prouvé avec grammaires hors contexte -. et $ \ {ww \ w mi \ in \ {a, b \} ^ * \} $