Como a regra 110 Turing está completa?

Li a página da wikipedia da regra 110 nos autômatos celulares e sei mais ou menos como elas funcionam (um conjunto de regras decide onde desenhar o próximo 1 ou 0).

Acabei de ler que Turing está completo, mas não consigo nem imaginar como você 'programaria' na 'regra 110'?

Universalidade é uma noção um tanto informal. O que isso significa aproximadamente é que, para cada função computável existe um "programa" no modelo, de modo que "executar" em qualquer entrada sempre "pára" e "gera" a resposta correta. (Observe que as máquinas de Turing não aparecem aqui: elas são apenas um exemplo de modelo de computação universal.)P P $f$$P$$P$$x$

As palavras citadas são aquelas que precisam ser definidas. Para máquinas de Turing:

• Um programa é especificado como uma lista de estados, um alfabeto de fita, um estado inicial, estados finais e transições.
• Executar uma máquina de Turing em uma entrada significa que inicializamos a fita com uma codificação de e executamos a máquina nessa fita de acordo com as regras usuais.x x $T$ $x$$x$$T$
• A Máquina de Turing pára se atingir um estado final. (Existem algumas variantes aqui.)
• O que a máquina de Turing produz (se parar) é o conteúdo da fita.

A regra 110, como modelo de computação, precisa ser definida formalmente da mesma maneira. Uma definição é razoável se for possível simular computacionalmente o modelo de computação, no seguinte sentido: existe uma função computável tal que para todo programa e entrada (ambos codificados como números naturais), pára se pára em , e se parar, sua saída é idêntica à saída de em .P x S ( P , x ) P x S ( p , x ) P $S$$P$$x$$S(P,x)$$P$$x$$S(p,x)$$P$$x$

Se você estiver curioso sobre a configuração específica da Regra 110 como um sistema de computação, sugiro que você dê uma olhada no artigo de Matthew Cook, que prova a universalidade da Regra 110 (ou melhor, de um sistema de computação construído em torno da Regra 110).

Quanto a outras regras, como a Regra 30 e a Regra 90, não sabemos que elas não são universais. Pode haver sistemas de computação convincentes construídos em torno deles que sejam universais, mas simplesmente não temos conhecimento de nenhum.

Da prova de Mateus:

A abordagem adotada aqui não é projetar um novo autômato celular, mas sim o mais simples que exibe naturalmente um comportamento complexo, e ver se podemos encontrar nesse comportamento complexo uma maneira de fazê-lo fazer o que queremos. Não nos preocuparemos diretamente com a tabela de pesquisa fornecida acima, mas, em vez disso, examinaremos o comportamento que é naturalmente exibido pela ação do autômato ao longo do tempo.

O autor começa por provar que um "sistema de tags" que remove 2 símbolos em cada etapa é universal, compilando um programa de máquina de turing de 2 estados. Depois disso, ele prova que um sistema de planador pode realmente implementar um sistema de tags. É um processo passo a passo. Em seguida, ele estuda o tempo espacial do CA-110 para encontrar os planadores e associá-los ao sistema de planadores corretamente.

Agora, para sua pergunta: como você 'programaria' na 'regra 110'?

1. Procure a máquina de turing de 2 estados mais simples e encontre as fitas das operações básicas OR, AND, XOR, NOT .

2. Compile-os no sistema de tags.

3. Compile a implementação do sistema de tags na implementação do planador.

4. Adapte-o aos planadores CA-110 corretamente e você terá as operações básicas em um autômato celular.

Os passos 1 a 4 são realizados apenas uma vez. A partir daí, calcular reduz a soma dos números usando portas lógicas.$1+1=2$

Uma nota à parte. Planadores são estruturas muito especiais. As operações serão vistas como partículas se movendo e colidindo (os planadores), gerando uma saída diferente dependendo de como esses planadores começam ou colidem.