Um computador pode simular-se como parte de um mundo simulado?

Digamos que você construa um computador que calcule o estado de todos os átomos no Universo em determinado momento futuro. Como o Universo é, por definição, tudo o que existe (e tudo o que interage com o resto), também inclui o computador que você está construindo. Você pode calcular o estado de todos os átomos no Universo usando o seu computador, incluindo os átomos do próprio computador?

Se tal computador não é possível por algum outro motivo teórico ou prático, o que é?

Não, um computador não pode simular-se perfeitamente além de outra coisa sem violar a teoria básica da informação : existem seqüências que não são compactáveis.

Aqui está a prova mais simples possível: suponha que o computador tenha um total de estados possíveis e suponha que exista algo fora do computador no universo; portanto, o universo possui pelo menos N + 1 possíveis estados distintos. Com zero de sobrecarga, cada estado do computador pode corresponder a um estado do universo, mas, como o universo tem mais estados do que o computador, alguns estados do universo serão mapeados para o mesmo estado do computador; nesse caso, a simulação será não conseguir distinguir entre eles.$N$$N+1$

Não tenho certeza se isso responde à sua pergunta, mas espero que seja significativa e leve a algum insight.

Suponha que exista uma máquina de turing que possa simular todos os átomos do universo, inclusive ele próprio, e então necessariamente possa simular-se.$X$

Agora, reduzir isso ao problema de parada é trivial:

Deixe tomar uma máquina de turing M como entrada e decida se ela pára ou não simulando o universo (uma vez que M está incluído no universo), faça o oposto (por exemplo, X pára se M não o fizer e volta para sempre se M parar ) Então X ( X ) demonstra uma contradição.$X$$M$$M$$X$$M$$M$$X(X)$

Essencialmente, isso significa que o melhor que o pode fazer para decidir se o X pára ou não é apenas correr por si mesmo (ou seja, deixar o universo funcionar do jeito que está), para simular o universo não dá uma vantagem.$X$$X$

O mesmo se aplica quando você deseja o estado do universo após o tempo . Como X não pode decidir se ele irá parar dentro de t tempo ou não dentro de t tempo (o mesmo argumento), então ele deixará o universo fazer isso. Tentar simular o universo fazendo isso, não pode reduzir o tempo que você levará para decidir. E se decidir como será o universo em t tempo leva mais que t , a simulação diverge (à medida que t vai para o infinito).$t$$X$$t$$t$$t$$t$$t$

Isso leva à conclusão de que apenas um simulador útil que decide como o universo será em tempo deve levar exatamente t tempo, ou seja, deixando o universo funcionar. Este simulador é, de fato, o simulador trivial.$t$$t$

Acho que poderíamos tentar ver isso como um problema de modelagem : como podemos reformular a questão para que ela se torne ciência da computação e não física? Vou tentar dar um exemplo simples e concreto de como podemos tentar fazer isso, para começar ...

Vamos substituir o "universo" por algo que é muito discreto e simples (e finito!). Digamos que nosso universo seja um autômato celular finito. Em particular, todo o mundo é um n × n grid.$W$$n \times n$

Suponha que a configuração inicial do mundo seja arbitrária. Agora, a pergunta parece ser a seguinte: Podemos escolher um subconjunto estrito C de W ("computador") e um estado inicial de C que atenda às seguintes condições:$W$$C$$W$$C$

• Nós não alterar o estado inicial de . (Ou seja, apenas "construímos nosso computador C ", sem alterar o mundo fora dele.)$W \setminus C$$C$

• Então, podemos executar qualquer número de etapas do autômato celular (o mundo inteiro , incluindo C e quaisquer interações entre W ∖ C e C ).$W$$C$$W \setminus C$$C$

• Podemos ler o estado atual do mundo por apenas inspecionando C . (Ou seja, C deve ser uma "simulação" de W. Observe que devemos ser capazes de ler o estado de W inteiro , não apenas W ∖ C. Em certo sentido, C deve ser capaz de simular tanto sua parte externa quanto interna. !)$W$$C$$C$$W$$W$$W \setminus C$$C$

Agora, isso é factível? Pode ser tentador usar um argumento de contagem (há mais estados em que em C ) e dizer que é impossível. Mas esse não é necessariamente o caso!$W$$C$

Vamos supor que nosso autômato celular é totalístico . Então, o que podemos fazer é simplesmente deixar ser a metade direita de nossa grade W e deixar a configuração inicial de C ser uma imagem espelhada de W ∖ C , para que tudo seja simétrico. É isso aí.$C$$W$$C$$W \setminus C$

Inicie o autômato e veja o que acontece. O estado atual de sempre será igual ao estado de C + sua imagem no espelho. Ou seja, apenas inspecionando C é suficiente para dizer o que é o estado de toda W .$W$$C$$C$$W$

(É claro que aqui o computador interage com e afeta o estado futuro de W ∖ C. Mas também é o que acontece no mundo real.)$W$$W \setminus C$

Agora, pode ser interessante ver se há uma resposta não trivial para essa pergunta. Por exemplo, quais autoridades de certificação admitem computadores com tamanho menor que a metade de ?$W$

Aqui está uma prova simples (não formal). Digamos que seja o ano de 2115 e eu tenho um computador de 100 anos que chamarei de Mac e um supercomputador de última geração chamado Deus. Deus pode simular e prever facilmente o Mac, até que eu faça o seguinte:

Primeiro, conecto uma webcam no Mac e aponto para a tela de Deus. Então, eu corro no Mac um programa que, em um loop infinito, armazena todos os números detectados na tela de Deus e gera e exibe um número que não está na lista de números armazenados. Por fim, peço a Deus que me mostre o número que Mac mostrará daqui a um minuto. Qualquer que seja o número que Deus mostre, o Mac produzirá e mostrará um número diferente; portanto, Deus será incapaz de dar uma resposta correta.

Isso é equivalente ao fato de que se um supercomputador me predizer, o que quer que ela me diga que eu farei, poderei fazer o oposto (como no comentário de Mark ). Além disso, isso ocorre independentemente do processo que o supercomputador usa para prever o futuro (simulação, viajando para o futuro e voltando, perguntando a um oráculo, etc.).

Um computador finito não pode simular a si próprio, ao contrário de uma máquina de Turing que possui uma fita infinita e pode simular qualquer outra máquina de Turing. No entanto, é possível simular qualquer computador em um computador semelhante, mas você precisa de um pouco mais de memória do que a "simulada" (como em uma máquina virtual): http://meaningofstuff.blogspot.com/2016/03/ pode-computador-ou-humano-simular-se.html