Clase de idiomas reconocibles por TM de 3 estados de cinta única

9

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).q0qacceptqreject

Para mayor comodidad, llame a la clase de lenguajes reconocibles por tales TM . Tengo varias preguntas sobre esta clase:C3

  1. ¿ ha estudiado previamente ?C3
  2. ¿ sabe que es igual a otras clases de complejidad / computabilidad de interés?C3
  3. Es la clase C3 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?
  4. ¿Cómo se relaciona C3 con la clase de lenguajes regulares, Regular ? (En particular, ¿está cada lenguaje regular en C3 ?)

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 C3 lugar de una clase similar pero diferente (el documento afirma probar que (1) cada lenguaje en C3 es decidible y (2) que C3 y Regularson 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.

Mikhail Rudoy
fuente
1
Si solo tiene un estado sin terminación y una cinta (cinta de entrada), su máquina no puede recordar nada de lo que leyó. Por lo tanto, puede aceptar o rechazar exactamente las entradas que contienen símbolos definidos del alfabeto de entrada.
David G
44
La máquina no puede recordar lo que leyó, pero puede reescribir lo que leyó con otra cosa. Así que realmente no veo por qué la caracterización que das sería correcta. (es decir, puedo pensar en una máquina simple que acepta y rechaza 011 ; aquí el comportamiento no está completamente determinado por los símbolos que están en la entrada). 01011
Mikhail Rudoy
1
Tienes razón, mi intuición estaba equivocada.
David G

Respuestas:

7

La bestia es extremadamente poderosa , por ejemplo, podemos construir un TM que acepte cada cadena del formularioM

LY={r0n1mAmn}

y rechaza cada cadena del formulario

LN={r0n1mAm>n}

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.rRAR

Descripción informal:

  • en escriba R y muévase a la derecha (prepárese para rechazar)rR
  • en escriba c y muévase a la derecha (moviéndose hacia el centro)0c
  • en escriba > y muévase a la izquierda (marque un 1 , prepárese para el próximo cruce de izquierda a derecha y vaya a la izquierda)1>1
  • en escriba < y muévase a la derecha (marque un 0 , prepárese para el siguiente cruce de derecha a izquierda y vaya a la derecha)c<0
  • en escribir > y vaya a la izquierda (cruce de izquierda a derecha, prepárese para el próximo de derecha a izquierda)<>
  • en escriba < y vaya a la derecha (cruce de derecha a izquierda, prepárese para el próximo de izquierda a derecha)><
  • en aceptar, en R rechazarAR
  • en blanco rechazarb

Ejemplo:

  :r 0 0 0 1 1 A
   R:0 0 0 1 1 A
   R c:0 0 1 1 A
   R c c:0 1 1 A
   R c c c:1 1 A
   R c c:c > 1 A
   R c c <:> 1 A
   R c c < <:1 A
   R c c <:< > A
   R c c:< > > A
   R c:c > > > A
   R c <:> > > A
   ...
   R c < < < <:A ACCEPT

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 YL ( 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)MLYLYL(M)LNL(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){r01A}=LY={r0n1mAmn}

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

L={12n}

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...b1b...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

Marzio De Biasi
fuente
1
Me gusta mucho la respuesta (+1). Sin embargo, la TM que se describe acepta un idioma diferente. Por ejemplo, acepta también las cadenas rrrrr00011AAAA, r000000r0000r0000r00011A, r00011A11111111 (después de A podría ser cualquier cosa en lugar de unos) ...
David G
@DavidG: ¡Tienes razón! No lo pensé demasiado ... Intento arreglarlo.
Marzio De Biasi
44
En realidad, incluso a través de no es el lenguaje reconocido por la TM descrita, ese lenguaje definitivamente no es regular: si esa TM es M , entonces L ( M ) r 0 1 A = L, entonces una breve prueba de contradicción (si L ( M ) es regular, entonces L ( M ) r 0 1 A = L también será regular; la contradicción) puede mostrar que L ( M ) no es regular.LML(M)r01A=LL(M)L(M)r01A=LL(M)
Mikhail Rudoy
3
@MikhailRudoy: sí! Yo tenía la misma idea. Abrí una teoría para editar la respuesta y vi tu comentario. Veamos si puedo reescribir la respuesta teniendo en cuenta su comentario ...
Marzio De Biasi
5

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

LY={a0n1mRm2n}

y rechaza cadenas de la forma:

LN={a0n1mRm<2n}

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.aAZZSS))Z

Las transiciones son:

  • en escriba R y muévase a la derecha (prepárese para rechazar)rR
  • en escriba Z y muévase a la derecha (moviéndose hacia el centro, establezca el contador binario en 0 ..)0Z
  • en escriba > y muévase a la izquierda (marque un 1 y disminuya el contador unario, prepárese para el próximo cruce de izquierda a derecha y vuelva al contador binario)1>1
  • en escriba < y vaya a la derecha (cruce de derecha a izquierda de la segunda mitad de la cadena, prepárese para el próximo de izquierda a derecha)><
  • en escribir > y ve a la izquierda (cruce de izquierda a derecha de la segunda mitad de la cuerda, prepárate para el siguiente de derecha a izquierda)<>
  • en escriba S y muévase a la derecha (transforme el dígito en uno y rebote hacia la derecha hacia el contador unario)ZS
  • en la escritura ) y muévase a la izquierda (borre el dígito y deje que la cabeza se mueva a la izquierda como un "acarreo", prepárese para la próxima izquierda a derecha de la primera parte)S)
  • encendido escriba Z y muévase a la derecha (establezca el cero que causará el rebote y deje que la cabeza se mueva a la derecha))Z
  • en aceptar, en R rechazarAR
  • en blanco rechazarb

Ejemplo:

 :a 0 0 0 1 1 1 1 1 1 1 1 R
  A:0 0 0 1 1 1 1 1 1 1 1 R
  A Z:0 0 1 1 1 1 1 1 1 1 R
  ...
  A Z Z Z:1 1 1 1 1 1 1 1 R
  A Z Z:Z > 1 1 1 1 1 1 1 R
  A Z Z S:> 1 1 1 1 1 1 1 R
  A Z Z S <:1 1 1 1 1 1 1 R
  A Z Z S:< > 1 1 1 1 1 1 R
  A Z Z:S > > 1 1 1 1 1 1 R
  A Z:Z ) > > 1 1 1 1 1 1 R
  A Z S:) > > 1 1 1 1 1 1 R
  A Z S Z:> > 1 1 1 1 1 1 R
  ...
  A Z S:Z > > > 1 1 1 1 1 R
  ...
  A Z S S < < <:1 1 1 1 1 R
  ...
  A S:) ) > > > > 1 1 1 1 R
  ...
 :A ) ) ) > > > > > > > > R ---> ACCEPT

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 YL ( M ) ) y no contiene cadenas de L N ( L ( M ) L N = ).L(M)LYLYL(M)LNL(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){r01A}

L(M){r01A}={a0n1mRm2n}=LY

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 ).LYCFLsLY01s2nLY

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).

Marzio De Biasi
fuente
Bueno, el lenguaje aquí es computable en una clase tan baja como coNLOGTIME, por lo que no requiere exactamente hipercomputación. (De hecho, y L N se pueden separar incluso en DLOGTIME.)LYLN
Emil Jeřábek
@ EmilJeřábek: Dije "no demasiado lejos" ... no reprima las ambiciones de esa pequeña clase ... :-)
Marzio De Biasi
2

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 ).C3C3C3C3C3C3

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 3C3C3LC3{1n;nN{0}}LLCC3Tambié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 nL para n 1 , entonces 1{}{ε}{1n;nN}{1n;nN{0}}C3LC31nLn1 para todos los m n . 1mLmnUn 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 .C3C3{1}C3C3


C3M{1n;nN{0}}1nnN{0}M

M

MM

MnAnAMAMMAM

M{1n;nN{0}}


C3M1nn1M1mmnM

M

MM1nn1n

MmAmAMAM1nMnA1nM no visita la celda directamente a la izquierda de la celda inicial, porque contiene el símbolo en blanco y, si lo lee, se ejecutará para siempre.

M{1m;mn}

David G
fuente
En primer lugar, en ninguna parte de la pregunta dice que M debe detener todas las entradas, por lo que arruina parte de la lógica en esta respuesta. Más allá de eso, la lógica en varios de los casos no tiene sentido para mí. Por ejemplo, en el caso 3, si M se mueve a la izquierda en blanco y A, entonces M visitará la celda directamente a la izquierda de la A más a la derecha (en contraste directo con el reclamo de la respuesta).
Mikhail Rudoy
Σ={1}k s.t. 1kL(M)L(M)={1nn>0}
@MikhailRudoy, ​​para aclarar primero el caso 3: si la cabeza se mueve hacia la izquierda en A y en el símbolo en blanco, se moverá hacia la izquierda para siempre y no se detendrá. Si alguna vez (digamos después de 100 pasos) visita la celda directamente a la izquierda de la A más a la derecha, en el caso de la entrada 1 nunca se detiene (en este caso la celda directamente a la izquierda de la A a la derecha contendrá el símbolo en blanco).
David G
@MikhailRudoy, ​​es cierto que supuse que una máquina de Turing tiene que detenerse. Editaré la respuesta para incluir también la posibilidad de que se ejecute para siempre. El resultado es similar.
David G
3
@MikhailRudoy: Por cierto, el problema de incubación es decidible para máquinas Turing de 1 estado; ver Gabor T. Herman, El problema de detención uniforme para máquinas de turing de un estado generalizadas . El modelo descrito allí es un poco diferente al suyo: el TM acepta si termina en una configuración mortal (no hay Aceptar / Rechazar); pero el resultado también se aplica a su modelo (simplemente detenga la TM en los símbolos que conducen a sus estados adicionales de aceptación / rechazo).
Marzio De Biasi