¿Es el problema de detención decidible para autómatas celulares unidimensionales de 3 símbolos?

10

He estado tratando de averiguar si el problema de detención es decidible para autómatas celulares unidimensionales de 3 símbolos.

Definición Sea la configuración del sistema en el paso de tiempo . Más formalmente , donde es el alfabeto.i f : A × NA Af(w,i)if:A×NAA

Definición. Un autómata celular se ha detenido en la configuración , si tenemos que .k N f ( w , i ) = f ( w , i + k )f(w,i)kNf(w,i)=f(w,i+k)

El problema de detención para un autómata celular dado es el siguiente:

Entrada: una palabra finita Pregunta: se detuvo el autómata en un estado ?sw
s

Los autómatas celulares elementales (con 2 símbolos) se definen aquí . Estoy enfocado en el mismo tipo de autómatas celulares, excepto que estoy interesado en el caso de CA con 3 símbolos en lugar de solo 2 símbolos.

De ahora en adelante, denotaré mis reglas en forma de , lo que significa que 3 símbolos vecinos producen otro debajo de ellos.

El problema de detención es decidible para autómatas celulares elementales de 2 símbolos.

Usaré para denotar un glóbulo blanco y para denotar uno negro.101

Si tenemos las reglas , , , sabemos que el autómata no se detendrá. Porque con la primera regla, dado que nuestra cuadrícula es infinita, siempre tendremos 3 celdas blancas que generarán una celda negra. Con la segunda y tercera reglas, la palabra se expandirá hacia los lados y el autómata nunca se detendrá.001 1 100 1000100111001

En el resto de los casos, podemos dejar que evolucione durante pasos y ver si se detiene. Si se detiene, entonces está bien, se detiene, si no lo hace, está repitiendo algunas combinaciones y está atrapado en un bucle, por lo que también podemos concluir que no se detendrá.2n

Lo que he descubierto para el caso de 3 símbolos

Es obvio que no se detendrá si tenemos las reglas o . Pero las reglas laterales de la forma y son más difíciles de analizar, porque ¿qué si tenemos las reglas y ?000 2 00 x y x 00 y 002 1 001 00001000200xyx00y00210010

Esto es lo que se me ocurrió:

Consideremos todas las combinaciones de tales reglas:

  1. 002 00010 y0020
  2. 002 10010 y0021
  3. 002 20010 y0022
  4. 002 00011 y0020
  5. 002 10011 y0021
  6. 002 20011 y0022
  7. 002 00012 y0020
  8. 002 10012 y0021
  9. 002 20012 y0022

No escribí los casos para las reglas de la forma , porque son simétricas.x00y

Entonces, en el primer caso, es obvio que la palabra de entrada no se expandirá a los lados, porque esas reglas de símbolos laterales producen ceros.

En los casos 5, 6, 8, 9 es obvio que el autómata nunca se detendrá, porque la palabra de entrada se expandirá.

Los casos 2,3,4,7 son más interesantes. Primero, tengamos en cuenta que el caso 2 es similar al caso 7 y el caso 3 es similar al caso 4. Entonces, consideremos los casos 2 y 3 por concisión.

Primero consideraré el caso 3, porque es más fácil.

Tenemos y . Es obvio que si el primer o el último símbolo de nuestra palabra de entrada es , entonces podemos concluir que el autómata no se detendrá. Pero si son '1', entonces tenemos que ver más cosas, en particular, echemos un vistazo a las reglas que pueden convertir el último o el primer símbolo en , porque si tenemos esos, luego de que produzcan ese , nosotros puede concluir que el autómata no se detendrá. (la palabra se expandirá a los lados).002 2 2 2 200100022222

Aquí están todas las combinaciones que debemos considerar:

010 011 012
 0   0   0
 0   0   1
 0   0   2
 0   1   0
 0   1   1
........... etc

Una explicación de lo que sucede si tenemos el primer triple de la tabla anterior

Tenemos una palabra , escrita en la cuadrícula. El primer y el último símbolo son . Digamos que tenemos las reglas , , (el primer triple) de arriba. Entonces sabemos que con cada próximo paso nuestra palabra de entrada se reducirá en 2 símbolos, porque estas reglas borran el primer y el último símbolo, pero si en algún momento obtenemos un , entonces la regla hará que la palabra crecer a un lado u otro (o ambos) y el autómata nunca se detendrá. Entonces, en general, en este caso podemos dejar que el autómata haga pasos, y si la palabra se vacía, entonces el autómata se detiene, si no, entonces no lo hace.1 010 0 011 0 012 0 2 002 2 | w | / 2w101000110012020022|w|/2

Caso generalizado 3

Lo generalicé y noté que simplemente podemos dejar que el autómata haga pasos y si en cualquiera de esos pasos tenemos un como primer o último símbolo, entonces el autómata no se detendrá. Si eso no sucede y el autómata aún no se detiene, entonces está repitiendo alguna configuración, por lo que está bloqueado en un bucle y no se detendrá. Si se detiene, entonces se detiene. 23n2

Donde me quedo atascado

Ahora consideremos el caso 2.

Tenemos las reglas y .002 100100021

Y aquí es donde me quedé atrapado y no sé qué hacer.

También escribí una tabla de reglas que comienza con . Los escribí porque parecían ser lo primero que debería analizar, porque incluso si tenemos la palabra de entrada con el primer o último símbolo (o ambos) como , en el siguiente paso, esos se convertirán en . Y tendremos que tratar con reglas de la forma .2 2 s 1 01 x y122s101xy

Aquí está la tabla:

010 011 012
 0   0   0
 0   0   1
 0   0   2
 0   1   0
 0   1   1
 0   1   2
 0   2   0
 0   2   1
 0   2   2
 1   0   0
 1   0   1
 1   0   2
 1   1   0
 1   1   1
 1   1   2
 1   2   0
 1   2   1
 1   2   2
 2   0   0
 2   0   1
 2   0   2
 2   1   0
 2   1   1
 2   1   2
 2   2   0
 2   2   1
 2   2   2

También es obvio que si entre nuestras 27 reglas, tenemos un triple de esta tabla en la que ninguna regla deriva un , entonces no tenemos nada de qué preocuparnos y simplemente podemos dejar que el autómata evolucione por pasos, porque ganó Realmente no se expande, ya que las reglas secundarias no producirán un .3 n 223n2

Pero mirando los triples que tienen un , en realidad es muy difícil de analizar, y si la palabra se expandirá o no también parece depender de la palabra de entrada.2

¿Pueden decirme cómo resolver esto? Parece que no puedo entender esto.

O, si este autómata celular de 3 símbolos se parece a algo para lo que se ha demostrado que el problema de detención es indecidible, ¿cómo puedo reducir ese algo a autómatas celulares de 3 símbolos?

Pavel
fuente
2
Los comentarios no son para discusión extendida; Esta conversación se ha movido al chat . Si surge algo de esta discusión, edite la pregunta para incorporar la nueva información o aclaraciones. No agregue las marcas "EDITAR": asegúrese de que un recién llegado pueda entender la pregunta sin tener que buscar en el historial.
Gilles 'SO- deja de ser malvado'

Respuestas:

1

Encontré este artículo: http://www.dna.caltech.edu/~woods/download/NearyWoodsMCU07.pdf y mostraré cómo demostrar que el problema de detención es indecidible para autómatas celulares de 15 símbolos.

Veamos las instrucciones típicas de una máquina Turing, tenemos:

1)q,xp,y,L

2)q,xp,y,R

El primero dice que si el autómata ve el símbolo en el estado , entonces reemplazamos por , cambiamos al estado y nos movemos hacia la izquierda, el segundo dice lo mismo, pero se mueve hacia la derecha.xqxyp

Asumamos que el alfabeto TM es , el conjunto de reglas es y el conjunto de estados es . Ahora, creemos un nuevo alfabeto para nuestro autómata celular, será el siguiente: . En otras palabras, en el nuevo alfabeto incluiremos el alfabeto de la TM, el alfabeto de estado de la TM y para cada estado , de modo que haya una regla incluiremos .ARQΣ=AQ{q|qrR,r=p,xq,y,L}qp,xq,y,Lq

El autómata modelará el TM, de la siguiente manera: en cada paso de la operación de CA tendremos un símbolo del alfabeto de estado del TM en la cinta de CA, y ese símbolo apuntará al símbolo al que estaría apuntando la cabeza de TM, en el siguiente manera: un símbolo que está a la derecha del símbolo de estado es el símbolo al que apunta la cabeza del TM. Como ejemplo, considere la cadena , digamos que , entonces la TM está en el estado , y la cabeza apunta al símbolo .s=...xabqzyk...qQqz

Veamos cómo podemos simular las operaciones de la TM. Consideremos primero el segundo:

2)q,zp,y,R

Así que, básicamente, si tenemos una cadena , se debe convertir en . Lo cual se puede lograr fácilmente agregando las siguientes reglas al autómata:s=...xabqzyk......xabypyk...

qzαp,αΣ

αqzy,αΣ

El primer caso es un poco más complicado, tenemos:

1)q,zp,y,L

Entonces, la cadena debe convertirse en , pero no hay una manera de hacer porque realizamos una operación TM mirando el estado y el símbolo, pero no nos informa sobre el símbolo, solo el estado, por lo que realizaremos este movimiento a la izquierda en 2 pasos:s=...xabqzyk......xapbyyk...abqpabq

primer paso:

qzαy,αΣ

αqzp,αΣ

segundo paso:

αβpp,α,βΣ

αpββ,α,βΣ

En cuanto a todas las demás reglas de CA, para las cuales no hay una regla en TM, escribiremos lo siguiente:

αβγβ,α,β,γΣ

Ahora que expliqué la forma de modelar el trabajo de TM en una CA, veamos por qué necesitamos 15 símbolos. En el documento, el enlace al que di arriba tenemos un TM universal con 6 estados y 4 símbolos:U6,4

ingrese la descripción de la imagen aquí

Por lo tanto, necesitamos todos los símbolos del alfabeto, que es 4, más todos los símbolos de estado que son 6 y todos los símbolos de estado manera que haya una regla , que son , entonces, necesitamos 15 símbolos en total. p , x q , y , L u 1 , u 3 , u 4 , u 5 , u 6qp,xq,y,Lu1,u3,u4,u5,u6

Entonces, ahora hay una brecha entre 2 y 15 símbolos (exclusivos), que no conocemos.

Pavel
fuente