Las máquinas de Turing de cinta única con entrada protegida contra escritura reconocen solo idiomas regulares

12

Aquí está el problema:

Demuestre que las máquinas de Turing de una sola cinta que no pueden escribir en la parte de la cinta que contiene la cadena de entrada reconocen solo los idiomas normales.

Mi idea es demostrar que esta TM en particular es equivalente a una DFA.

Usar este TM para simular DFA es muy sencillo.

Sin embargo, cuando quiero usar este DFA para simular TM, me encuentro con el problema. Para la transición TM , DFA puede simular definitivamente leyendo la cinta a la derecha y haciendo la misma transición de estado.δ(q,a)=(q,a,R)

Para , no puedo entender cómo usar este DFA o NFA para simular el movimiento a la izquierda porque el DFA solo lee a la izquierda y no tiene pila ni algo para almacenar.δ(q,a)=(q,a,L)

¿Debo considerar otra forma? ¿Alguien podría darme algunas pistas? Gracias.

usuario3273554
fuente
2
Primero debes tener cuidado con la lógica / significado de tus oraciones. Su título implica que solo tiene que demostrar que cualquier idioma reconocido por la máquina xxx Turing es regular. No es necesario que demuestre lo contrario: cualquier lenguaje normal es reconocido por dicha máquina (aunque eso sea obvio). Entonces su 4to párrafo "Usando ..." es irrelevante para la pregunta como se indicó. Luego, en el quinto, usa "este DFA", aparentemente refiriéndose al DFA del párrafo anterior, que ya no tiene nada que ver con el problema en cuestión. Tiene una TM y debe encontrar un DFA aún desconocido.
babou
3
Una pista: es posible que desee buscar la noción de "secuencias cruzadas". Además, es posible que desee probar que es equivalente a un NFA (con un conjunto de estados más grande). Como calentamiento, imagine que la cabeza de la TM va 10 pasos hacia la derecha, luego 3 pasos hacia la izquierda, y luego siempre a la derecha a partir de ahí, ¿podría construir un NFA para simular el conjunto de entradas que una TM puede reconocer a lo largo de dicha cabeza? ¿movimiento?
DW
1
@babou Permitir escribir fuera del área de entrada no da todo RE en mi opinión. Esto se debe a que no he encontrado una manera de construir la función de transición que permita copiar la entrada al área en blanco fuera del área de entrada original. Si eso es posible sin NUNCA escribir en el área de entrada original, entonces claramente uno puede trabajar en el lado derecho de la entrada al igual que una TM normal que nos proporciona todos los idiomas RE.
Informado A
1
@DW No entiendo cómo las "secuencias cruzadas" por sí mismas resolverán este problema. En realidad, no los usé directamente, sino solo mediante el uso de la equivalencia de 2NFA y NFA, pero esta equivalencia es solo una parte de la prueba. Por cierto, ya que parece conocer el problema, ¿sabría de dónde viene, ya que no puedo encontrar referencias en Internet? El resultado realmente me sorprendió, y me pregunto por qué no parece interesar a nadie.
babou
1
@DW ¿Pensó que esto era una repetición de la equivalencia de la FSA estándar y la FSA de 2 vías, o conoce el origen de este problema: TM que no escribe en su entrada ? Me pregunto por qué nadie respondió en 9 meses, y por qué fue preguntado por un estudiante aparentemente novato.
babou

Respuestas:

11

Introducción

Pensé que podría haber un error en la declaración original de la pregunta, y el OP ya no estaba disponible para preguntar. Así que supuse que la cinta era de solo lectura en todas partes, y escribí una primera prueba basada en esa suposición, motivada por el hecho de que la TM tiene un poder de Turing completo fuera de la parte de entrada de la cinta si puede escribirla, lo que induce el falso creencia de que puede reconocer cualquier lenguaje RE.

Sin embargo, ese no es el caso: la restricción en la escritura en la parte de entrada de la cinta implica que solo se puede extraer información finita de la entrada, limitada por el número de estados en la entrada y salida de esa parte de la cinta (combinado con lado de entrada y salida). Se debe acreditar a InstructedA por comentar en un comentario que hay un problema con el reconocimiento de cualquier lenguaje RE, ya que no es posible hacer una copia de la entrada sin NUNCA escribir en el área de entrada original,

Por lo tanto, escribí una segunda prueba que asume que solo la sección de entrada de la cinta es de solo lectura, el resto está permitido de lectura-escritura.

Aquí mantengo ambas pruebas, ya que la primera me ayudó a encontrar la solución, aunque no es necesario entender la segunda prueba, es más compleja y está subsumida por la segunda prueba. Se puede omitir. Sin embargo, la prueba más débil tiene la ventaja de ser constructiva (para obtener un FSA equivalente a la máquina de Turing), mientras que el resultado más general no es constructivo.

Sin embargo, estoy dando primero el último y más poderoso resultado. Estoy un poco sorprendido de que no haya podido encontrar este resultado, incluso sin pruebas, en otra parte de la red, o preguntando a algunos usuarios competentes, y cualquier referencia al trabajo publicado sería bienvenida.

Contenido:

  • Las máquinas de Turing que no sobrescriben la entrada aceptan solo idiomas normales. Esta prueba no es constructiva.

  • Las máquinas de Turing con cintas de solo lectura aceptan solo idiomas normales. Puede omitirse como subsumido por pruebas anteriores, pero utiliza un enfoque diferente, que tiene la ventaja de ser constructivo.

Las máquinas de Turing que no sobrescriben la entrada solo aceptan idiomas normales

Recordamos que, aunque la TM no sobrescribe su entrada, y por lo tanto se lee solo en su entrada, la TM puede leer y escribir en el resto de la cinta . La prueba se basa en el hecho de que el comportamiento de observación de la TM sobre una entrada desconocida puede producir solo un número finito de casos diferentes. Por lo tanto, aunque el TM tiene todo el poder de Turing simplemente confiando en el resto de su cinta, su información en la entrada, que puede ser cualquier cadena en , es finita, por lo que solo puede computar en un número finito de diferentes casos. Esto proporciona una visión diferente del carácter finito de los lenguajes regulares, más conductuales que estructurales.Σ

Suponemos que la TM acepta cuando entra en un estado de aceptación.

Prueba.

Definimos un cómputo restringido de entrada (IRC) como un cómputo ( solo lectura) de la TM de modo que el cabezal TM permanezca en la parte de entrada de la cinta, excepto posiblemente por la última transición que puede moverlo a una celda inmediatamente en el izquierda o derecha del área de entrada.

Un cálculo restringido de entrada izquierda es un IRC que comienza en el símbolo más a la izquierda de la entrada. Un cálculo restringido de entrada derecha es un IRC que comienza en el símbolo más a la derecha de la entrada.

Primero demostramos que, para los cálculos restringidos de entrada izquierda que comienzan en el estado , los siguientes idiomas son regulares:p

  • el lenguaje de las cadenas de entrada de modo que haya un cálculo restringido de entrada a la izquierda, comenzando en el estado , que termina en la primera celda a la izquierda del símbolo de entrada más a la izquierda en el estado ;KLpLqpq

  • el lenguaje de las cadenas de entrada de modo que haya un cálculo restringido de entrada a la izquierda, comenzando en el estado , que termina en la primera celda a la derecha del símbolo de entrada más a la derecha en el estado ;KLpRqpq

  • el lenguaje de las cadenas de entrada de modo que haya un cálculo restringido de entrada a la izquierda, comenzando en el estado , que alcanza un estado de aceptación.ALpp

Y de manera similar, para los cálculos restringidos de entrada derecha que comienzan en el estado , los siguientes lenguajes definidos de manera similar son regulares: , y .pKRpLqKRpRqARp

Las 6 pruebas se basan en el hecho de que los autómatas de estado finito no deterministas de dos vías (2NFA) reconocen conjuntos regulares (ver Hopcroft + Ullman 1979, pp 36-41, y el ejercicio 2.18 página 51). Un 2NFA funciona como un TM de solo lectura en una cinta limitada a su entrada, comenzando inicialmente desde el símbolo más a la izquierda y aceptando moviéndose más allá del extremo derecho en un estado de aceptación.

En cada uno de los 6 casos, la prueba se realiza construyendo un 2NFA que imita los cálculos restringidos de entrada, pero con algunas transiciones adicionales para asegurarse de que puede comenzar desde la celda más a la izquierda y aceptar el lenguaje saliendo desde el extremo derecho en una aceptación estado. Para los idiomas , el estado de aceptación original de la TM se cambia a estados que conducen a un cálculo de no aceptación detenido. En dos casos, puede ser necesario agregar una celda adicional con un nuevo símbolo de protección a la izquierda para detectar los cálculos de TM que terminarían en el extremo izquierdo, a fin de hacer que terminen en el extremo derecho.K????

Estos lenguajes se definen para todas las combinaciones de estados y de la máquina Turing original. Representan todo lo que la TM puede observar (por lo tanto, conocido y calculado) de la entrada.pq

Sik4k2K????2kA??4k2+2k

4k2+2kΣ4k2+2k

PΣ24k2+2k

uvPuvP

Para ser muy completo, omitimos el caso de la cadena de entrada vacía. En este caso, solo tenemos una TM normal, que puede leer o escribir en cualquier lugar. Si alcanza un estado de aceptación, la cadena vacía está en el idioma, de lo contrario no lo está. Pero eso tiene poco efecto sobre el hecho de que el idioma reconocido es regular.

Por supuesto, no es decidible si una clase de equivalencia está o no en el idioma (lo mismo vale para la cadena vacía). Esta es una prueba no constructiva.

QED

Las máquinas de Turing con cintas de solo lectura aceptan solo idiomas normales

Esto está subsumido por el resultado anterior. Se mantiene ya que utiliza un enfoque diferente, probablemente menos elegante, y me ayudó a encontrar la prueba anterior al comprender lo que importa. Pero bien puede ser omitido por los lectores. Sin embargo, una ventaja de esta prueba es que es una prueba constructiva que produce una FSA que acepta el lenguaje. Hendrik Jan proporciona un boceto de una prueba similar en su respuesta a una pregunta similar anterior , que supone que toda la cinta fue de solo lectura.

El primer paso de la prueba es mostrar que el cabezal no necesita abandonar el área de entrada de la cinta. Por lo tanto, analizamos qué sucede cuando la cabeza se mueve fuera del símbolo de entrada más a la derecha. El análisis al salir del extremo izquierdo es idéntico.

q

  1. TM mantiene la computación para siempre, sin que la cabeza vuelva a la parte de entrada de la cinta;

  2. el TM alcanza un (a) de aceptación o (b) se detiene en un estado de no aceptación;

  3. r

q

10

0

Representamos la parte relevante del control de estado finito mediante un gráfico dirigido donde los vértices son los estados de la TM y donde los bordes son las transiciones en blanco, con un peso +1 o -1 dependiendo de si se supone que la cabeza se mueve derecha o izquierda.

ARq

ER(q,r)1qr

qA

p,aR,qp,aR,qAqAR

p,aR,q(q,r)ERp,aS,rS

aFa={(p,r) there is a dummy transition p,aS,r}FaFar,aL,s(p,r)Fap,aL,s

+11

qA

Ahora tenemos que hacer algunos cambios cosméticos, para que este TM se comporte exactamente como un NDA bidireccional (la aceptación es solo al salir de la entrada de la derecha a un estado eclipsante). Entonces podemos confiar en la equivalencia conocida entre 2-NDA y FSA (ver, por ejemplo, Hopcroft + Ullman 1979, página 40) para obtener la prueba de que el idioma es regular.

QED

babou
fuente
0

Moverse hacia la izquierda o hacia la derecha no es un problema, ya que los autómatas finitos bidireccionales reconocen con exactitud los idiomas regulares (esto no es obvio). Sin embargo, si su TM puede escribir fuera de la parte de la cinta de la palabra de entrada, creo que puede usar esta parte de la cinta para reconocer en idiomas regulares. Tal vez no entiendo claramente la pregunta.

nevro
fuente
Esto realmente no parece una respuesta. Por cierto, el comentario anterior de DW sobre "secuencias de cruce" es exactamente sobre el tema: se utilizan para mostrar que 2DFA (2way det FA) reconoce conjuntos regulares. Aquí el único problema es que el TM puede deambular por las partes en blanco de la cinta. Si puede evitar eso, entonces se queda con un 2DFA o un 2NFA. Creo que puede reducir una TM a otra TM que no deambula por el blanco, utilizando también "secuencias cruzadas".
babou