Uma versão barulhenta do jogo da vida de Conway suporta computação universal?

Citando a Wikipedia , "[O Jogo da Vida de Conway] tem o poder de uma máquina de Turing universal: ou seja, qualquer coisa que possa ser computada algoritmicamente pode ser computada no Jogo da Vida de Conway".

Esses resultados se estendem a versões barulhentas do Jogo da Vida de Conway? A versão mais simples é que, após cada rodada, todas as células vivas morrem com uma pequena probabilidade cada célula morta se torna viva com uma pequena probabilidade s (independentemente).$t$$s$

Outra possibilidade é considerar a seguinte variante probabilística da regra do próprio jogo.

• Qualquer célula viva com menos de dois vizinhos vivos morre com probabilidade .$1-t$
• Qualquer célula viva com dois ou três vizinhos vivos vive com probabilidade para a próxima geração.$1-t$
• Qualquer célula viva com mais de três vizinhos vivos morre com probabilidade .$1-t$
• Qualquer célula morta com exatamente três vizinhos vivos se torna uma célula viva com probabilidade .$1-t$

Pergunta: Essas versões barulhentas do Jogo da Vida ainda suportam cálculos universais? Caso contrário, o que se pode dizer sobre o seu "poder computacional"?

Informações relacionadas sobre o poder computacional de autômatos celulares e versões ruidosas de autômatos celulares também serão muito apreciadas.

(Esta questão foi desenvolvida a partir desta questão no MathOverflow. A resposta de Vincent Beffara no MO deu referências interessantes para resultados relacionados sobre aspectos computacionais de autômatos celulares barulhentos.)

Aqui estão algumas referências "nas proximidades", para o que vale a pena. Parece que o caminho a seguir é reduzi-lo a uma questão sobre "máquinas de Turing barulhentas", que foram estudadas (um pouco recentemente) e que aparentemente são a área relevante mais próxima da literatura. A resposta básica / geral / razoável parece ser que, se a MT pode resistir / corrigir ruídos (como é demonstrado nessas referências), é bem provável que a CA também possa, dentro de alguns limites / limites.

A questão de como reduzir uma "CA barulhenta" para uma "TM barulhenta" (e vice-versa) é mais aberta. Pode não ser difícil, mas parece não haver pesquisas publicadas na área. Outra questão é que a TM ruidosa é um novo modelo e, portanto, pode haver várias maneiras (naturais?) De representar uma TM ruidosa. Por exemplo, os documentos a seguir examinam as interrupções na função de transição de estado, mas outro modelo natural são as interrupções nos símbolos das fitas (o último sendo mais conectado a CAs ruidosas?). Pode haver alguma relação entre os dois.

• Máquina de Turing tolerante a falhas por Ilir Capuni, 2012 (tese de doutorado)

  A máquina de Turing é o modelo universal de computação mais estudado. Esta tese estuda a questão de saber se existe uma máquina de Turing que possa calcular de maneira confiável mesmo quando violações de sua função de transição ocorrem independentemente uma da outra, com uma pequena probabilidade.

  Nesta tese, provamos a existência de uma máquina de Turing que, com uma sobrecarga polinomial, pode simular qualquer outra máquina de Turing, mesmo quando está sujeita a falhas do tipo acima, respondendo à pergunta que ficou aberta por 25 anos.

• Uma máquina de Turing resistindo a rajadas isoladas de falhas de Ilir Capuni e Peter Gacs, 2012
• Máquinas ruidosas de Turing de Eugene Asarin e Pieter Collins, 2005

Gil está perguntando se o GL está esquecendo tudo sobre sua configuração inicial no tempo, independentemente do tamanho, quando cada célula "desobedece" à função de transição independentemente de outras células com alguma probabilidade pequena.

Que eu saiba, isso não é conhecido pelo GL. É uma pergunta muito interessante. Se puder suportar o barulho, deve preservar sua universalidade.

Uma rápida visão geral do estado da arte é a seguinte.

1. A regra de Toom pode salvar para sempre um pouco as falhas que ocorrem independentemente uma da outra, com uma pequena probabilidade.
2. Acreditava-se amplamente (as conjecturas de taxas positivas) que todos os CA com 1 dim são ergódicos até P. Gacs construir seu CA em escala múltipla que pode simular qualquer outro CA com sobrecarga moderada, mesmo quando sujeito ao ruído acima mencionado.
3. A questão se a regra G (acs) K (urdiumov) L (evin) pode economizar um pouco para sempre na presença do ruído acima ainda está aberta. O Kihong Park - um estudante de Gacs - mostrou que não, quando o barulho é enviesado.
4. Quando o trabalho em 2 foi publicado, M. Blum perguntou se uma TM pode continuar seu cálculo se a cada etapa, a transição não é feita de acordo com a função de transição com uma pequena probabilidade, independentemente de outras etapas, assumindo que as informações armazenadas em a fita longe da cabeça não se deteriora. Uma resposta positiva foi dada por I. Capuni (outro aluno do Gacs) em 2012.

Para iniciantes, lembre-se de que a pesquisa no Jogo da Vida de Conway ainda está em andamento e os desenvolvimentos futuros podem apresentar uma solução muito menos complicada.

Agora, então. Curiosamente, este é um tópico que está realmente de acordo com a biologia e a física quântica e com a ciência da computação tradicional. A questão que está na raiz do problema é se algum dispositivo pode resistir efetivamente a alterações aleatórias em seu estado. A resposta pura e simples é que é impossível fabricar uma máquina que seja perfeitamenteresistente a tais mudanças aleatórias. Certamente, isso é verdade da mesma maneira que a mecânica quântica pode causar eventos aparentemente impossíveis. O que impede que esses eventos ocorram (levando a maioria das pessoas a declará-los estritamente impossíveis) é a probabilidade estupendamente pequena de que esse evento ocorra. Uma probabilidade tornada tão pequena pela grande diferença de escala entre o nível quântico e o nível humano. Da mesma forma, é possível fabricar uma máquina de estado resistente a pequenos graus de mudança aleatória, simplesmente tornando-a tão grande e redundante que qualquer "mudança" observada é efetivamente zero, mas a suposição é de que esse não é o objetivo. Supondo que isso possa ser realizado da mesma maneira que animais e plantas são resistentes à radiação ou danos físicos.

A questão pode não ser como impedir que distúrbios de baixo nível causem muito dano, mas como recuperar o máximo de dano possível. É aqui que a biologia se torna relevante. Animais e plantas realmente têm essa capacidade no nível celular (observe: estou falando de células no sentido biológico nesta resposta) Agora, no jogo da vida de Conway, a noção de construir um dispositivo de computação na escala de células únicas é atraente (afinal de contas, torna essas criações muito menores e mais eficientes), mas, embora possamos construir computadores auto-reprodutores ( consulte Gemini ), isso ignora o fato de que o próprio objeto construtor pode ser danificado por distúrbios.

Outra maneira mais flexível de resolver isso é criar computadores a partir de partes redundantes que se auto-reproduzem (pense em células biológicas) que executam suas operações, se reproduzem e são substituídas.

Nesse ponto, podemos ver outro paralelo interessante no mundo real. Esses distúrbios de baixo nível são semelhantes aos efeitos da radiação. Isso é mais apreciável quando você considera o tipo de dano que pode ser causado aos autômatos celulares. É fácil desencadear a falha em cascata ou a "morte" de uma célula no Jogo da Vida de Conway, da mesma forma que acontece com muitas células expostas à radiação. Mas existe a pior possibilidade de mutação, criando uma célula "cancerígena" que continua a reproduzir cópias defeituosas de si mesma que não auxiliam no processo computacional ou produzem resultados incorretos.

Como eu disse, é impossível construir um sistema totalmente à prova de falhas, você só pode tornar cada vez menos provável que uma falha comprometa todo o sistema. Naturalmente, a questão fundamental aqui é realmente "são simulações probabilísticas próprias de Turing completas", que já foram decididas como verdadeiras . Eu teria respondido a essa pergunta fundamental inicialmente, exceto que não foi o que você perguntou.

Lembro-me de xkcd 505: Um monte de pedras .

Qualquer computador do mundo real está sujeito a algum nível de ruído. Uma simulação de um computador universal no universo ideal de Vida infinita de Conway terá um tempo médio entre falhas, dependente dos detalhes de engenharia de seu design. Ele calculará de forma confiável por um período quantificável probabilisticamente, de maneira confiável por um período de acumulação de erros e, em seguida , de modo algum .

Eu esperaria que uma lógica nebulosa ou um modelo de superposição quântica demonstrasse claramente qual confiabilidade deve ser esperada de uma construção específica. Pode-se simular as saídas esperadas de vários componentes, em vez de iterar sobre todas as suas células, em qualquer grau em que possam ser isoladas uma da outra. É possível quantificar a interferência esperada de componentes com falha. Um algoritmo genético deve ser a melhor maneira de desenvolver componentes de tolerância a falhas, resistência e correção com MTBFs tão grandes quanto o desejado para uma determinada distribuição de ruído.