¿Puede una computadora simularse a sí misma como parte de un mundo simulado?

Digamos que construyes una computadora que calculará el estado de todos los átomos en el Universo en cierto momento futuro. Debido a que el Universo es, por definición, todo lo que existe (y todo lo que interactúa con el resto), también incluye la computadora que está construyendo. ¿Puedes calcular el estado de todos los átomos en el Universo usando tu computadora, incluidos los átomos de la computadora misma?

Si tal computadora no es posible por alguna otra razón teórica o práctica, entonces, ¿qué es?

No, una computadora no puede simularse perfectamente además de otra cosa sin violar la teoría de la información básica : existen cadenas que no son compresibles.

Aquí está la prueba más simple posible: suponga que la computadora tiene un total de estados posibles, y suponga que hay algo fuera de la computadora en el universo, por lo que el universo tiene al menos N + 1 estados distintos posibles. Con cero sobrecarga, cada estado de la computadora puede corresponder a un estado del universo, pero dado que el universo tiene más estados que la computadora, algunos estados del universo se asignarán al mismo estado de la computadora, en cuyo caso la simulación será No ser capaz de distinguir entre ellos.$N$$N+1$

No estoy seguro de si esto responde a su pregunta, pero espero que sea significativa y conduzca a una idea.

Supongamos que hay una máquina de Turing que puede simular cada átomo en el universo, incluido él mismo, entonces necesariamente puede simularse a sí mismo.$X$

Ahora, reducir eso al problema de detención es trivial:

Dejar $X$ tome una máquina de Turing como su entrada y decida si se detiene o no simulando el universo (ya que M está incluido en el universo), luego haga lo contrario (por ejemplo, X se detiene si M no lo hace, y realiza un bucle para siempre si M se detiene ) Entonces X ( X ) demuestra una contradicción.$M$$M$$X$$M$$M$$X(X)$

Esencialmente, esto significa que lo mejor que puede hacer para decidir si X se detiene o no es simplemente ejecutándose (es decir, dejando que el universo funcione a su manera), por lo que simular el universo no da una ventaja.$X$$X$

Lo mismo se aplica cuando desea el estado del universo después de time. Dado que X no puede decidir si se detendrá dentro de t tiempo o no dentro de t tiempo (mismo argumento), entonces le permitirá al universo hacerlo. Intentar simular el universo haciéndolo, no puede reducir el tiempo que tomará para decidir. Y si decidir cómo se verá el universo en t tiempo lleva más de t, entonces la simulación divergerá (a medida que t va al infinito).$t$$X$$t$$t$$t$$t$$t$

Esto lleva a la conclusión de que solo un simulador útil que decida cómo se verá el universo en tiempo debe tomar exactamente t tiempo, es decir, dejando que el universo funcione. Este simulador es, de hecho, el simulador trivial.$t$$t$

Supongo que podríamos tratar de ver esto como un problema de modelado : ¿cómo podemos reformular la pregunta para que se convierta en informática y no en física? Trataré de dar un ejemplo simple y concreto de cómo podríamos intentar hacer esto, para comenzar las cosas ...

$W$$n \times n$

Suponga que la configuración inicial del mundo es arbitraria. Ahora la pregunta parece ser la siguiente: ¿Podemos elegir un subconjunto estricto $W$$C$$W$$C$

• No cambiamos el estado inicial de $W \setminus C$$C$

• Entonces podemos ejecutar cualquier número de pasos del autómata celular (todo el mundo , incluyendo C y cualquier interacción entre$W$$C$$W \setminus C$$C$

• Podemos leer el estado actual del mundo simplemente inspeccionando C . (Es decir, C debe ser una "simulación" de W. Tenga en cuenta que debemos ser capaces de leer el estado de W completo , no solo$W$$C$$C$$W$$W$$W \setminus C$$C$

$W$$C$

$C$$W$$C$$W \setminus C$

$W$$C$$C$$W$

$W$$W \setminus C$

Ahora puede ser interesante ver si hay una respuesta no trivial a esta pregunta. Por ejemplo, qué CA admiten computadoras que tienen tamaño$W$

Aquí hay una prueba simple (no formal). Digamos que es el año 2115 y tengo una computadora de 100 años que llamaré Mac, y una supercomputadora de última generación llamada Dios. Dios puede simular y predecir fácilmente Mac, hasta que haga lo siguiente:

Primero, adjunto una cámara web a Mac y la apunto hacia la pantalla de Dios. Luego, ejecuto en Mac un programa que, en un bucle infinito, almacena cada número detectado en la pantalla de Dios y genera y muestra un número que no está en la lista de números almacenados. Finalmente, le pido a Dios que me muestre el número que Mac mostrará dentro de un minuto. Cualquier número que Dios muestre, Mac producirá y mostrará uno diferente, por lo que Dios no podrá dar una respuesta correcta.

Esto es equivalente al hecho de que si una supercomputadora me predice, cualquier cosa que ella me diga que haré, podré hacer lo contrario (como en el comentario de Mark ). Además, esto se mantiene independientemente del proceso que utiliza la supercomputadora para predecir el futuro (simulación, viajar al futuro y regresar, pedir un oráculo, etc.).

Una computadora finita no puede simularse a sí misma, en contraste con una máquina de Turing que tiene una cinta infinita y puede simular cualquier otra máquina de Turing. Sin embargo, es posible simular cualquier computadora en una computadora similar, pero necesita un poco más de memoria que la "simulada" (como en una máquina virtual): http://meaningofstuff.blogspot.com/2016/03/ can-computer-or-human-simulate-yourself.html