un tiempo he sentido curiosidad por las máquinas de Turing con exactamente una cinta y exactamente 3 estados (es decir, el estado inicial , el estado de aceptación y el estado de rechazo ). Tenga en cuenta que permito alfabetos de cinta arbitrarios (finitos) (es decir, el alfabeto de cinta no está restringido para que sea igual al alfabeto de entrada).
Para mayor comodidad, llame a la clase de lenguajes reconocibles por tales TM . Tengo varias preguntas sobre esta clase:
- ¿ ha estudiado previamente ?
- ¿ sabe que es igual a otras clases de complejidad / computabilidad de interés?
- Es la clase robusta a los cambios en el modelo. Por ejemplo, si se permite que las TM utilizadas permanezcan en su lugar durante una sola transición (en lugar de moverse siempre hacia la izquierda o hacia la derecha) o si la cinta se hace infinita en ambas direcciones en lugar de solo hacia la derecha, la clase de idiomas reconocibles por cambio de TM de 3 cintas de 1 estado?
- ¿Cómo se relaciona con la clase de lenguajes regulares, ? (En particular, ¿está cada lenguaje regular en ?)
Una búsqueda (más bien superficial) trajo solo esta publicación cs.stackexchange que es relevante pero no responde mis preguntas y este documento , que no he leído con suficiente detalle para asegurarme de que se trata exactamente de la clase lugar de una clase similar pero diferente (el documento afirma probar que (1) cada lenguaje en es decidible y (2) que y son clases distintas con intersección no vacía). Como se señaló en los comentarios de la publicación cs.stackexchange, este tipo de TM puede considerarse como un autómata celular muy particular, por lo que tal vez alguien que conozca la literatura sobre la teoría del autómata celular podría ayudar.
fuente
Respuestas:
La bestia es extremadamente poderosa , por ejemplo, podemos construir un TM que acepte cada cadena del formularioM
y rechaza cada cadena del formulario
La idea es transformar la primera en R y luego dejar que la cabeza llegue al centro de la cuerda y luego hacer un zig-zag "sin estado"; si alcanza A antes de R, entonces acepta.r R A R
Descripción informal:
Ejemplo:
Esta técnica de zig-zag se usa en la máquina Turing universal de 2 estados más pequeña (tiene 18 símbolos) construida por Rogozhin (Rogozhin 1996. TCS, 168 (2): 215–240)).
Se debe prestar cierta atención para demostrar que detiene en todas las entradas (solo tenga en cuenta que rechaza en la entrada en blanco y todos los símbolos que no se detienen "convergen" a < o > que no pueden conducir a un bucle infinito).M < >
Como comentó DavidG, el lenguaje reconocido por M es un superconjunto de L Y (es decir, L Y ⊂ L ( M ) ) pero no contiene ninguna cadena de L N (es decir, L ( M ) ∩ L N = ∅ ) y, como comentó MikhailRudoy, esto es suficiente para demostrar que L ( M ) no es regular.L(M) M LY LY⊂L(M) LN L(M)∩LN=∅ L(M)
De hecho, si es regular, entonces también L ( M ) ∩ { r 0 ∗ 1 ∗ A } = L Y = { r 0 n 1 m A ∣ m ≤ n } sería regular (que no es por una simple aplicación del lema de bombeo); conduciendo a una contradicción.L(M) L(M)∩{r0∗1∗A}=LY={r0n1mA∣m≤n}
Entonces no es regular .L(M)
... Pero como todos los superhéroes, tiene un talón de Achille: ni siquiera puede reconocer el regular:C3
Informalmente puede usar solo el extremo izquierdo ( b es el símbolo en blanco) o el rightmist 1 b . . . como un gancho y "expandirse" en la otra dirección; pero el Aceptar o Rechazar final no puede estar en el símbolo en blanco del lado opuesto, por lo que solo se puede hacer en la parte interna de los 1 sy a partir de una entrada lo suficientemente larga, puede ser "falso" extendiéndolo por uno.b1... b 1b... 1
Finalmente, después de leer el documento, puedo confirmar que el TM de un estado descrito en él coincide con su clase ... (así que no hay nada nuevo aquí :-) ... y el lenguaje utilizado por el autor para demostrar que contiene Los idiomas no regulares son muy similares a los míos.C3
fuente
Subestimé el poder de ... ¡en realidad no está muy lejos de la hipercomputación !C3
(Publico esto como una respuesta separada para mayor claridad)
Podemos construir una máquina Turing de estado único que acepte las cadenas del formulario:M
y rechaza cadenas de la forma:
La idea y la construcción son similares a las de la respuesta anterior: transformar la primera en A , dejar que la cabeza llegue al centro de la cadena y luego hacer un zig-zag "sin estado", pero las transiciones "implementan" un "contador binario" "en la primera mitad de esta manera: en Z (Cero) rebota la cabeza hacia la derecha y convierte la Z en S (Uno) la próxima vez que la cabeza llegue a S , transfórmala en a ) y deja que la cabeza mover hacia la izquierda; cuando los alcances de la cabeza los ) transformarlo a un Z . La segunda mitad de la cadena se comporta como un contador unario.a A Z Z S S ) ) Z
Las transiciones son:
Ejemplo:
Se debe prestar cierta atención para demostrar que detiene en todas las entradas (solo tenga en cuenta que rechaza en la entrada en blanco y todos los símbolos que no se detienen "pasan" ( , S , Z o < , > que no pueden conducir a un bucle infinito) )M (,S,Z <,>
El lenguaje es un superconjunto de L Y ( L Y ⊂ L ( M ) ) y no contiene cadenas de L N ( L ( M ) ∩ L N = ∅ ).L(M) LY LY⊂L(M) LN L(M)∩LN=∅
Suponga que está libre de contexto , luego, mediante las propiedades de cierre de las CFL, la intersección con el lenguaje regular { r 0 ∗ 1 ∗ A } produce un lenguaje CF:L(M) {r0∗1∗A}
Pero con una simple aplicación del Lema de Ogden para CFL podemos demostrar que : simplemente elija un s ∈ L Y lo suficientemente largo y marque todos los 0 s; se puede bombear al menos un cero y cualquiera que sea el número de 1 s en la cadena de bombeo, el crecimiento exponencial de 2 n conduce a una cadena ∉ L Y ).LY∉CFL s∈LY 0 1s 2n ∉LY
Entonces no está libre de contexto .L(M)
... ahora me pregunto si esta es otra respuesta para "reinventar la rueda", o si es un resultado nuevo (pequeño).
fuente
En esta respuesta se supone que las máquinas de Turing tienen cintas infinitas en ambos sentidos. Los reclamos no son válidos para cintas infinitas de un solo sentido.
Permítanme definir primero la clase de lenguajes como la clase de todos los idiomas que pueden decidir las máquinas Turing de una cinta con 3 estados ( C 3 se definió como la clase de lenguajes reconocibles por las máquinas Turing de una cinta con 3 estados). Introduje la clase C ′ 3 porque en mi respuesta original, inconscientemente cambié las clases C 3 y C ′ 3 (solo consideré la clase C ′ 3 ).C′3 C3 C′3 C3 C′3 C′3
Esta respuesta es más un complemento a las respuestas de @MarzioDeBiasi. Mostró que las clases y C ' 3 no están contenidas en CFL y, por lo tanto, contienen lenguajes bastante interesantes. Sin embargo, como mostraré en esta publicación, cada lenguaje L en C ′ 3 tiene la propiedad de que el conjunto { 1 n ; n ∈ N ∖ { 0 } } es o bien en L o en su complemento L C . Así C ′ 3C3 C′3 L C′3 {1n;n∈N∖{0}} L LC C′3 También es muy restrictivo, por ejemplo. contiene solo idiomas triviales unarios , { ε } , { 1 n ; n ∈ N } y { 1 n ; n ∈ N ∖ { 0 } } . La clase C 3 contiene un poco más de lenguajes unarios. Sin embargo, sostiene que si L ∈ C 3 y 1 n ∈ L para n ≥ 1 , entonces 1{} {ε} {1n;n∈N} {1n;n∈N∖{0}} C3 L∈C3 1n∈L n≥1 para todos los m ≥ n . 1m∈L m≥n Un corolario simple es que no todos los lenguajes regulares están en ni en C ′ 3 . Además, el lenguaje{1}no está en C 3 ni en C ′ 3 .C3 C′3 {1} C3 C′3
fuente