Un MPA (autómata multipebble) es un 2DFA (autómata finito determinista bidireccional) que puede usar un número arbitrario de guijarros (en realidad, como máximo guijarros en una entrada dada - la entrada está escrita en la cinta entre dos extremos -marcadores como ). Durante el cálculo, un MPA puede detectar si el símbolo debajo de la cabeza tiene un guijarro, y luego puede poner un guijarro (quitar el guijarro) si no hay guijarro (un guijarro).w # w #
σ k > 0 es un homomorfismo, donde es un símbolo .
Para cualquier lenguaje determinista sensible al contexto no es difícil demostrar que existe un tal que pueda ser reconocido por un MPA. Entonces, hablando libremente, podemos decir quek > 0 h k ( L )
cualquier "problema" decidible por un DTM de espacio lineal (máquina de Turing determinista) puede ser resuelto por un MPA.
¿También es cierto para cualquier idioma en ? ¿Pueden las AMP decidir todos los lenguajes deterministas sensibles al contexto?
es la longitud de .
es el símbolo de , donde. w 1 ≤ i ≤ | w |
.
fuente
Respuestas:
Quizás pueda construir un lenguaje en DPSACE (n) que no pueda ser reconocido por un MPA con usando un argumento de diagonalización (probablemente la idea es similar a la de la respuesta de Ben, pero no profundicé en ello):k=1
Suponga que sobre el alfabeto codifica un MPA usando una lista de transiciones:Σ={0,1}
donde es el estado actual, es el símbolo actual, es el estado del guijarro, es el nuevo estado, es el nuevo estado del guijarro, es la dirección del movimiento, es un marcador final).a p s ′ p ′ L | R #s a p s′ p′ L|R #
Una máquina Turing en la entrada puede verificar si es una descripción válida de un y simularla en la entrada para pasos usando celdas, estirando la entrada de esta manera:x M P A x x 4 | x | 6 | x | + log | x |M x MPAx x 4|x| 6|x|+log|x|
Dónde:
Si detiene en pasos, TM genera lo contrario (si no detiene produce 0).MPAx 4|x| M M
Para suficientemente grande , los pasos de simulación son mayores queque es mayor que la longitud de una descripción de configuración completa de ; de esta manera, si el no se detiene en pasos, entonces estamos seguros de que se repetirá para siempre.x>x0 4|x| 2|x|+2|x|log|x| MPAx MPAx 4|x|
Suponga que hay un que decide el mismo lenguaje de , entonces siempre se detiene y puede construir un más grande " que decide el mismo idioma, con (solo agregue estados dum).MPAy L M MPAy′ y′>x0
Por construcción tenemos, cual es una contradicción.MPAy′(y′)=1−M(y′)=1−MPAy′(y′)
fuente
No. Contraejemplo: el problema de detención de las AMP es decidible en el espacio lineal: si la AMP tiene N estados, necesitamos | k | +2 bits de espacio para almacenar las ubicaciones de los guijarros, registrar N bits para almacenar el estado actual y bits para almacenar un contador; Si el contador realiza ciclos, la máquina simulada nunca se detendrá. Esto es lineal en | k | (ignorando el espacio O (N \ log N) requerido para describir la máquina), según sea necesario.log(N(|k|+2))+|k|+2
Dado que este lenguaje es decidible en el espacio lineal, también se puede expresar como DCSL.
fuente