O problema da parada é decidível para autômatos celulares unidimensionais de três símbolos?

Eu tenho tentado descobrir se o problema de parada é decidível para autômatos celulares unidimensionais de três símbolos.

Definição Deixe denotar a configuração do sistema no momento da etapa . Mais formalmente , onde é o alfabeto.i f : A ∗ × N → A ∗$f(w,i)$$i$$f:A^*\times \mathbb{N} \to A^*$$A$

Definição. Um autômato celular parou na configuração , se tivermos que .∀ k ∈ N f ( w , i ) = f ( w , i + k $f(w,i)$$\forall k\in \mathbb{N}$$f(w,i)=f(w,i+k)$

O problema de parada para um determinado autômato celular é o seguinte:

Entrada: uma palavra finita Pergunta: o autômato irá parar em alguns estados ?$w$
$s$

Autômatos celulares elementares (com 2 símbolos) são definidos aqui . Estou focado no mesmo tipo de autômato celular, exceto que estou interessado no caso de CAs com 3 símbolos em vez de apenas 2 símbolos.

A partir de agora, denotarei minhas regras na forma de , significando que três símbolos vizinhos produzem outro abaixo deles.$***\to*$

O problema da parada é decidível para autômatos celulares elementares de 2 símbolos

Usarei para denotar uma célula branca e para denotar uma célula preta.$0$$1$

Se tivermos as regras , , , sabemos que o autômato não será interrompido. Porque com a primeira regra, como nossa grade é infinita, sempre teremos 3 glóbulos brancos que gerarão uma célula preta. Com a segunda e a terceira regra, a palavra será expandida para os lados e o autômato nunca será interrompido.001 → 1 100 → $000 \to 1$$001 \to 1$$100 \to 1$

No restante dos casos, podemos deixá-lo evoluir por etapas e ver se ele pára. Se parar, tudo bem, ele pára, se não parar, está repetindo algumas combinações e fica preso em um loop, para que possamos concluir também que não irá parar.$2^n$

O que eu descobri para o estojo de 3 símbolos

É óbvio que isso não será interrompido se tivermos as regras ou . Mas as regras laterais da forma e são mais difíceis de analisar, porque o que se temos regras e ?000 → 2 00 x → y x 00 → y 002 → 1 001 → $000 \to 1$$000 \to 2$$00x \to y$$x00 \to y$$002 \to 1$$001 \to 0$

Aqui está o que eu vim com:

vamos considerar todas as combinações de tais regras:

1. 002 → $001 \to 0$ e$002 \to 0$
2. 002 → $001 \to 0$ e$002 \to 1$
3. 002 → $001 \to 0$ e$002 \to 2$
4. 002 → $001 \to 1$ e$002 \to 0$
5. 002 → $001 \to 1$ e$002 \to 1$
6. 002 → $001 \to 1$ e$002 \to 2$
7. 002 → $001 \to 2$ e$002 \to 0$
8. $001 \to 2$ e$002 \to 1$
9. $001 \to 2$ e$002 \to 2$

Não escrevi os casos para as regras do formato , porque são simétricas.$x00 \to y$

Portanto, no primeiro caso, é óbvio que a palavra de entrada não será expandida para os lados, porque essas regras de símbolos laterais produzem zeros.

Nos casos 5, 6, 8, 9, é óbvio que o autômato nunca irá parar, porque a palavra de entrada estará se expandindo.

Os casos 2,3,4,7 são mais interessantes. Primeiro, vamos observar que o caso 2 é semelhante ao caso 7 e o caso 3 é semelhante ao caso 4. Portanto, vamos considerar os casos 2 e 3 por questões de concisão.

Vou considerar o caso 3 primeiro, porque é mais fácil.

Temos e . É óbvio que, se o primeiro ou o último símbolo de nossa palavra de entrada for , podemos concluir que o autômato não será interrompido. Mas se eles são '1', então temos que examinar mais coisas, em particular, vamos ver regras que podem transformar o último ou o primeiro símbolo em , porque se os tivermos, depois que eles produzirem esse , podemos concluir que o autômato não irá parar. (a palavra será expandida para os lados).$001 \to 0$$002 \to 2$$2$$2$$2$

Aqui estão todas as combinações que precisamos considerar:

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

Uma explicação do que acontece se tivermos o primeiro triplo da tabela acima

Temos uma palavra , escrita na grade. O primeiro e o último símbolo são . Digamos que temos as regras , , (a primeira tripla) acima. Então, sabemos que, a cada passo seguinte, nossa palavra de entrada ficará menor em 2 símbolos, porque essas regras apagam o primeiro e o último símbolos, mas se em algum momento obtivermos , a regra fará com que a palavra crescer para um lado ou para o outro (ou ambos) e o autômato nunca irá parar. Portanto, nesse caso, podemos deixar que o autômato faça etapas, e se a palavra ficar vazia, o autômato pára, se não, então não.$w$$1$$010 \to 0$$011 \to 0$$012 \to 0$$2$$002 \to 2$$|w|/2$

Caso generalizado 3

Eu o generalizei e notei que podemos simplesmente deixar o autômato executar etapas e se em qualquer uma dessas etapas tivermos como primeiro ou último símbolo, o autômato não parará. Se isso não acontecer e o autômato ainda não parar, está repetindo algumas configurações, por isso fica preso em um loop e não pára. Se parar, então pára.$3^n$$2$

Onde eu fico preso

Agora vamos considerar o caso 2.

Temos as regras e .$001 \to 0$$002 \to 1$

E aqui é onde eu fiquei preso e não sei o que fazer.

Também escrevi uma tabela de regras que começa com . Escrevi isso porque parecia ser a primeira coisa que eu deveria analisar, porque mesmo se tivermos a palavra de entrada com o primeiro ou o último (ou ambos) símbolo como , na próxima etapa esses se transformarão em . E teremos que lidar com regras no formato .$1$$2$$2's$$1$$01x \to y$

Aqui está a tabela:

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

Também é óbvio que, se dentre nossas 27 regras, tivermos um triplo dessa tabela em que nenhuma regra deriva a , não teremos nada com que nos preocupar e podemos simplesmente deixar o autômato evoluir por etapas, porque ganhou realmente expandir, uma vez que as regras paralelas não produzirão um .$2$$3^n$$2$

Mas olhando para os triplos que têm um , é realmente muito difícil de analisar e se a palavra se expandirá ou não também parece depender da palavra de entrada.$2$

Vocês podem me dizer como resolver isso? Parece que não consigo entender isso.

Ou, se esse autômato celular de três símbolos se parece com algo pelo qual o problema de parada foi indecidível, como posso reduzir esse valor para três autômatos celulares?

Encontrei este artigo: http://www.dna.caltech.edu/~woods/download/NearyWoodsMCU07.pdf e mostrarei como provar que o problema da parada é indecidível para autômatos celulares de 15 símbolos.

Vejamos as instruções típicas de uma máquina de Turing, temos:

1)$q,x\to p,y,L$

2)$q,x\to p,y,R$

O primeiro diz que, se o autômato vê o símbolo no estado , substituímos por , mudamos para o estado movemos para a esquerda, o segundo diz a mesma coisa, mas se move para a direita.$x$$q$$x$$y$$p$

Vamos supor que o alfabeto TM é , o conjunto de regras é e o conjunto de estados é . Agora, vamos criar um novo alfabeto para nosso autômato celular, será o seguinte: . Em outras palavras, no novo alfabeto incluiremos o alfabeto da MT, o alfabeto de estado da MT e para cada estado , de modo que exista uma regra , incluiremos .$A$$R$$Q$$\Sigma=A\bigcup Q\bigcup \{q'|\forall q \exists r\in R, r=p,x\to q,y,L\}$$q$$p,x\to q,y,L$$q'$

O autômato modelará a TM, da seguinte maneira: em cada etapa da operação da CA, teremos um símbolo do alfabeto de estado da TM na fita da CA, e esse símbolo apontará para o símbolo que a cabeça da TM apontaria, no da seguinte maneira: um símbolo que está à direita do símbolo de estado é o símbolo para o qual a cabeça da TM aponta. Como exemplo, considere a sequência , digamos, que , então a TM está no estado , e a cabeça aponta para o símbolo .$s=...xabqzyk...$$q\in Q$$q$$z$

Vamos ver como podemos simular as operações da TM. Vamos considerar o segundo primeiro:

2)$q,z\to p,y,R$

Então, basicamente, se temos uma string , deve ser convertido em . O que pode ser alcançado com muita facilidade adicionando as seguintes regras ao autômato:$s=...xabqzyk...$$...xabypyk...$

$qz\alpha\to p, \forall \alpha \in \Sigma$

$\alpha qz\to y, \forall \alpha \in \Sigma$

O primeiro caso é um pouco mais complicado, temos:

1)$q,z\to p,y,L$

Portanto, a string deve ser convertida em , mas não há como fazer porque realizamos uma operação de TM observando estado e símbolo, mas não nos fala sobre o símbolo, apenas o estado, portanto, executaremos esse movimento à esquerda em duas etapas:$s=...xabqzyk...$$...xapbyyk...$$abq\to p$$abq$

Primeiro passo:

$qz\alpha\to y, \forall \alpha \in \Sigma$

$\alpha qz\to p', \forall \alpha \in \Sigma$

segundo passo:

$\alpha \beta p'\to p, \forall \alpha, \beta \in \Sigma$

$\alpha p' \beta\to \beta, \forall \alpha, \beta \in \Sigma$

Quanto a todas as outras regras de CA, para as quais não existe uma regra na TM, escreveremos o seguinte:

$\alpha \beta \gamma \to \beta, \forall \alpha,\beta,\gamma \in \Sigma$

Agora que expliquei a maneira de modelar o trabalho da TM em uma CA, vamos ver por que precisamos de 15 símbolos. No artigo, o link ao qual acima, temos uma TM universal com 6 estados e 4 símbolos:$U_{6,4}$

Portanto, precisamos de todos os símbolos do alfabeto, que são 4, além de todos os símbolos de estado, que são 6, e todos os símbolos de estado modo que exista uma regra , que são , então precisamos de 15 símbolos no total. p , x → q , y , L u 1 , u 3 , u 4 , u 5 , u $q'$$p,x\to q,y,L$$u_1, u_3, u_4, u_5, u_6$

Então, agora existe uma diferença entre 2 e 15 símbolos (exclusivos), dos quais não sabemos.