Estoy estudiando la teoría de la computación, y sé que hay lemas bombeos para lenguajes regulares y libres de contexto, pero ¿por qué no idiomas recurrentemente enumerable? ¿Hay algo acerca de una máquina de Turing que haría imposible un lema bombeo? Mi conjetura es que no importa cómo usted la bomba una cadena, una máquina de Turing puede reconocerlo siempre, pero estoy seguro.
Respuestas
¿Demasiados anuncios?
user27515
Puntos
214
Parte del problema es que la Emt se les permite ir hacia atrás a través de sus cintas. Esto hace que inventar un Lema de Bombeo difícil por una razón básica.
Recordemos que la principal prueba del Lema de Bombeo para regular idiomas fue a tomar un DFA $D$$L$, y luego contar el número de las configuraciones locales (los números de estados multiplicado por el tamaño de las letras del alfabeto). Si $D$ lee cualquier cadena en $L$ de longitud mayor que este, entonces no debe ser un (estado,símbolo) par a la que se llega dos veces. Por el "bombeo" de la subcadena que aparece entre los tiempos de $D$ en estos dos estados, la definición de un DFA deja en claro que $D$ debe hacer exactamente lo mismo cada vez que a través de cada una de estas bombas.
Para Pda el razonamiento es similar.
Tenga en cuenta que si usted intentó hacer lo mismo para un TM $M$ puede ejecutar en un problema, ya que podría haber sido que los pasos entre llegar a la misma (estado,símbolo) par leer un símbolo a la izquierda de la subcadena. A continuación, el bombeo no puede trabajar porque se mueve a la izquierda en una bomba puede resultar en una acción diferente llevando a cabo (porque no hay ninguna garantía de que el último símbolo de esta bombeado subcadena es el mismo como el último símbolo antes de esta bomba, y puede que tenga que tener en cuenta, incluso antes de símbolos, sólo agravan el problema). Así que no sólo sería una prueba de Bombeo Lema tener en cuenta el local (estatal,con el símbolo de configuración, pero en realidad la configuración completa sería necesario. De esta manera, el conjunto de configuraciones que necesitan ser distinguidos llega a ser ilimitado, y así el palomar argumento falla.
JoshL
Puntos
290
La razón es que el contexto libre y regular los idiomas son reconocidos por la mayoría simple de los tipos de autómatas que tienen limitaciones sobre cómo utilizar su memoria, mientras que una máquina de Turing no tienen esas limitaciones.
Por ejemplo, un lenguaje regular es reconocible por una máquina de estados finitos. La máquina de estados finitos no tiene memoria, aparte de saber en qué estado se encuentra. Por lo tanto, si ejecuta una máquina de estados finitos el tiempo suficiente, se debe entrar en el mismo estado dos veces. Pero, puesto que no tiene ninguna manera de saber que ha estado en ese estado antes, no tiene manera de saber si ha sido en ese estado dos veces, cinco veces o mil veces. Esta es la forma en que el lema de bombeo para regular idiomas se demostró que podemos engañar a la máquina de estados finitos por lo que es ir a través de varios pasos que deje en el mismo estado en que se encontraba originalmente, y no tiene manera de saber que esto ha sucedido.
El lema de bombeo para lenguajes libres de contexto es similar. Estos son aceptados por el pushdown autómatas. La limitación en la memoria de una pushdown autómata es que el autómata sólo puede tener en cuenta el elemento de la parte superior de la pila - se puede saber la profundidad de la pila es inferior a la parte superior del elemento. Podemos utilizar esta limitación de engañar al autómata mediante la adición o eliminación de la información de la pila, manteniendo el elemento de la parte superior de la misma. El automoaton no se puede pedir la profundidad de la pila, por lo que no tiene manera de saber que hemos cambiado.
Recursivamente enumerable de las lenguas aceptadas por máquinas de Turing. Una máquina de Turing no tiene ninguna limitación en cuanto a cómo se puede utilizar la cinta de la memoria. Puede grabar cada paso que toma, y volver la mirada sobre todos los pasos en cualquier momento. Así, no hay ninguna manera de que podamos engañar a la máquina de Turing en la forma en que se puede engañar a una máquina de estados finitos o pushdown autómata.
user2566092
Puntos
19546
Una máquina de Turing puede decidir como el conjunto de todas las cadenas que consisten en $N$ subcadenas cada consecutivo 0 y de 1 consecutivos que se alternan donde las subcadenas tienen longitud $1,2,3,..,N$, para algún número natural $N$ (el lenguaje es la Unión sobre todo posible $N$). Es difícil imaginar cualquier tipo de bombeo lema que podía manejar ese lenguaje.
ml0105
Puntos
8033
Supongamos que tengo $L = \{ <M>,w :$ M es un TM que se detiene en w $\}$. Claramente este es recursivamente enumerable. No es regular, aunque, tampoco es de contexto libre. El lema de bombeo para regular y lenguajes libres de contexto decirle que si usted tiene una cadena en el lenguaje, la construcción de la cadena, pero manteniendo el patrón se mantenga en la nueva cadena en el lenguaje.
Así que si tengo una FSA, simplemente puedo mantener un bucle o de ida y vuelta entre un par de los estados para construir una cadena de longitud deseada. Regular lenguajes de contexto libre de gramáticas, por lo que la intuición es la misma. Una Máquina de Turing es más sofisticado de lo que se puede aceptar. Tenga en cuenta que la programación de una Máquina de Turing es como escribir código máquina (no de la asamblea, pero en código de máquina).
