Son máquinas de Turing más potente que los autómatas de pila?

Question

He venido con un resultado al leer algunos libros de autómatas, que las máquinas de Turing parecen ser más poderoso que los autómatas de pila. Puesto que la cinta de una máquina de Turing siempre se puede hacer que se comporte como una pila, sería parece que en realidad podemos afirmar que la EMT son más poderosos.

¿Es esto cierto?

Answer 1

Si sólo tenemos en cuenta que 'las máquinas de Turing siempre se pueden hacer a comportarse como una pila' sólo se puede concluir que son al menos tan potente como autómatas de pila.

Pero, en general, sí es cierto, las máquinas de Turing son más poderosos que los PDA. El ejemplo más fácil sería para demostrar que las máquinas de Turing pueden describir lenguaje sensible al contexto.

Answer 2

Usted no puede ir a la parte inferior de la pila sin "olvidar" el resto de la pila. Con una máquina de Turing se puede ir fácilmente de ida y vuelta en la cinta.

Esta sencilla tarea no se puede hacer con un transductor de pila (más o menos lo mismo que los autómatas de pila, pero que puede escribir cosas en cada paso), pero se puede hacer fácilmente con una cinta:

Leer una cadena $ w $ y luego escribir la cadena dos veces: $ $ ww

Si no quiere oír hablar de transductores, el problema similar es para usted: este lenguaje se reconoce fácilmente por una máquina de Turing, pero no con un autómata de pila:

$$ L = \ {ww \ mediados w \ en S ^ * \} $$

pero creo que con un transductor a tener una idea de la diferencia.

Answer 3

máquinas de Turing son de hecho más poderoso que PDAs regulares.

Sin embargo, en caso especial de una PDA con dos pilas (TPDA o 2-PDA) la TPDA es igualmente potente que un autómatas de Turing.

La idea básica es que se puede simular la cinta del TM usando dos pilas: en la pila todo izquierda está almacenado que se deja de la cabeza en la Turing-cinta, mientras que el símbolo bajo la cabeza y todo bien de la cabeza es almacenado en la otra pila. Y así el TPDA puede simular el trabajo de una máquina de Turing, y son equivalentes. Una descripción un poco más detallada se puede encontrar aquí .

Answer 4

Un máquina de Turing es más poderoso que un de pila autómata - que es un teorema fundamental de la teoría de autómatas y puede ser probado en un número de maneras. Por ejemplo, el problema de la parada de los TM es indecidible - no existe un programa (u otro TM) que siempre va a dar una correcta sí o no hay respuesta a la pregunta: ¿este TM en este cese de entrada. Pero para PDA, el problema de la parada es solucionable. Por lo que los modelos tienen poder intrínsecamente diferentes, el modelo TM tiene más poder que el modelo de PDA, pero también "sufre" para ello.

Pero dos de pila autómatas "trabajar juntos" puede simular una máquina de Turing. Sólo tenemos que especificar lo que entendemos por dos PDAs trabajando juntos - ambos están conectados a la cadena de entrada y cada obra lata con su pila de forma independiente de la otra. Sus controles de estados finitos también están conectados, o de manera equivalente, se combinaron en un único control de estado finito.

La prueba de que va más o menos que cada uno de los PDAs pueden simular la mitad de la cinta de la TM, es decir, la parte de las memorias de traducción a partir de cinta de la plaza casa y salir indefinidamente hacia la izquierda o hacia la derecha. Los detalles se pueden obtener una desordenado poco, pero la idea básica es simple. La parte superior del almacenamiento de pila "izquierda" representa la plaza actual jefe de la TM y la parte inferior izquierda representa la plaza activa de la cinta del TM; de manera similar para el "derecho" almacenamiento de pila. En cuanto a movimientos, por ejemplo, cuando el TM mueve un cuadrado a la izquierda, la combinación de la simulación de las PDA hace estallar un símbolo de almacenamiento de pila correcto y lo empuja hacia la parte superior del almacenamiento de pila izquierda. Cuando el TM vuelve a escribir el símbolo en virtud de su cabeza, la pda izquierda aparece su símbolo superior (el valor antes) y empuja hacia atrás otro símbolo (el nuevo valor).

Así que la combinación de dos PDAs trabajar de esta manera tiene exactamente la misma potencia que los TM, y el problema de la parada para el combo también es indecidible.

Answer 5

Just exhiben una TM aceptar $ 0 ^ n 1 ^ n 2 ^ n $, que contexto isnt't libre (y por lo tanto no hay PDA aceptarla).

Answer 6

La prueba habitual es uno con desvío.

1. Demostrar que los autómatas de pila-aceptar exactamente el idiomas libre de contexto, el conjunto de las lenguas aceptadas por las gramáticas libres de contexto. (Que se encuentra en cualquier libro de texto sobre la materia)
2. Tenga en cuenta que las máquinas de Turing aceptan todos los idiomas recursivas (por definición).
3. Demostrar que los lenguajes libres de contexto son un subconjunto propio de los lenguajes recursivos, por ejemplo a través de Pumping Lemma - - que ha demostrado con facilidad en las gramáticas libres de contexto -. y $ \ {ww \ mediados w \ in \ {a, b \} ^ * \} $