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

30

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

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

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

Gil Kalai
fonte
2
@vzn 1) não, essa não é a "verdadeira questão", é uma questão completamente diferente; A pergunta de Gil é sobre a robustez de um modelo computacional simples ao ruído, não sobre o poder da aleatoriedade; 2) TMs com uma fita aleatória não são mais poderosos do que TMs deterministas, consulte esta resposta: cstheory.stackexchange.com/a/1415/4896
Sasho Nikolov
2
A verdadeira questão aqui é se as versões estocásticas / ruidosas do "Jogo da Vida" ainda suportam a computação. (Se essas versões suportam cálculos em P, seu poder pode chegar até o BPP.) É possível que o poder computacional dessas versões estocásticas do jogo da vida seja muito menor.
Gil Kalai
3
Talvez eu esteja afirmando o óbvio, mas você pode duplicar uma configuração o suficiente para garantir com alta probabilidade que uma versão da configuração nem sequer tenha uma célula invertida. Minha crença pessoal é que podemos fazer muito, muito melhor, mas pelo menos é um simples limite inferior.
user834
4
Não sei se a pergunta está bem definida. Suponha que . Parece-me que você poderá encontrar um computador que lide com todos os erros de um bit no "Jogo da Vida", fornecendo computação tolerante a falhas, a menos que você espontaneamente obtenha um grande bloco de erros de uma só vez. Mas acho que nada pode ser robusto contra todos os erros. Por exemplo, suponha que os erros criem espontaneamente um adversário malévolo, determinado a interromper o cálculo. Você pode mostrar que seu cálculo é bem-sucedido com probabilidade > 1 - 10 - 9, mas falha com probabilidade > 10 - 10000 . Isso conta?t=109>1109>1010000
Peter Shor
2
Peter, se seu cálculo for bem-sucedido com probabilidade 2/3, estou feliz.
Gil Kalai

Respostas:

8

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
(Outra pergunta: poderia haver alguma conexão entre TMs ruidosas e máquinas de Turing probabilísticas ?)

vzn
fonte
7

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.
user8719
fonte
"Se não for ergódico, preservará sua universalidade" ... você tem alguma evidência para essa afirmação? Isso é um teorema? Onde está provado? Acredito que o trabalho de Gacs mostra que isso é verdade em pelo menos um caso, mas não vejo como isso prova o que é válido para o jogo da vida de Conway.
Peter Shor
Obrigado por apontar. Não é um teorema, mas uma questão aberta interessante. Não ser ergódico parece pouco para pedir uma afirmação tão forte.
user8719
3

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.

Hawkwing
fonte
Uau! Obrigado pelo voto drive-by-down! De qualquer forma, revisei minha postagem, adicionando algumas informações e fontes. Desculpe, não tive tempo para fazer isso quando publiquei isso pela primeira vez. Eu poderia modificar essa resposta ainda mais para se adequar aos padrões da comunidade, se não fosse pelo fato de não haver razão para o voto negativo.
Hawkwing
5
Como não eleitor, não vejo como isso responde à pergunta de Gil. Você aborda a questão de se "qualquer dispositivo pode efetivamente resistir a alterações aleatórias em seu estado", que não é o que Gil perguntou.
András Salamon
Obrigado (desta vez não sarcasticamente) pelo comentário, András Salamon. Eu mesmo votaria útil, mas ainda sou um novo usuário neste site excedente. De qualquer forma, desculpe-me por minha resposta parecer fora de tópico. Talvez eu tenha abordado a questão de maneira mais vaga do que pretendia, mas sinto que minha resposta responde à pergunta original, respondendo a uma pergunta semelhante e depois traçando paralelos entre as duas. Talvez isso seja uma maneira indireta de responder?
Hawkwing
0

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.

user130144
fonte
(votação misteriosa aqui) Uma resposta quantitativa seria muito especulativa. Não pode haver uma resposta mais precisa do que "sim, condicionalmente" sem extensas experiências em alguma implementação escolhida de um UTM. Um computador normal em um ambiente de alta radiação ainda é praticamente um UTM, mesmo que apenas brevemente.
user130144