Un ordinateur peut-il se simuler dans le cadre d'un monde simulé?

Disons que vous construisez un ordinateur qui calculera l'état de tous les atomes de l'Univers à un certain moment dans le temps. Parce que l'Univers est, par définition, tout ce qui existe (et tout ce qui interagit avec le reste), il comprend également l'ordinateur que vous construisez. Pouvez-vous calculer l'état de tous les atomes de l'Univers à l'aide de votre ordinateur, y compris les atomes de l'ordinateur lui-même?

Si un tel ordinateur n'est pas possible pour une autre raison théorique ou pratique, quel est-il?

Non, un ordinateur ne peut pas parfaitement se simuler en plus de quelque chose d'autre sans violer la théorie de l'information de base : il existe des chaînes qui ne sont pas compressibles.

Voici la preuve la plus simple possible: supposons que l'ordinateur ait un total de états possibles, et supposons qu'il y ait quelque chose en dehors de l'ordinateur dans l'univers, donc l'univers a au moins N + 1 états distincts possibles. Avec zéro surcharge, chaque état de l'ordinateur peut correspondre à un état de l'univers, mais comme l'univers a plus d'états que l'ordinateur, certains états de l'univers seront mappés au même état de l'ordinateur, auquel cas la simulation sera ne pas pouvoir les distinguer.$N$$N+1$

Je ne suis pas sûr que cela réponde à votre question, mais j'espère que cela pourrait être significatif et conduire à un aperçu.

Supposons qu'il existe une machine de Turing qui peut simuler chaque atome de l'univers, y compris lui-même, elle peut alors nécessairement se simuler.$X$

Maintenant, réduire cela au problème d'arrêt est trivial:

Soit prenant une machine de Turing M comme entrée et décide si elle s'arrête ou non en simulant l'univers (puisque M est inclus dans l'univers), puis fait le contraire (par exemple X s'arrête si M ne le fait pas, et boucle pour toujours si M s'arrête ). Alors X ( X ) montre une contradiction.$X$$M$$M$$X$$M$$M$$X(X)$

Essentiellement, cela signifie que le meilleur peut faire pour décider si X s'arrête ou non simplement en s'exécutant lui-même (c'est-à-dire en laissant l'univers fonctionner à sa manière), donc simuler l'univers ne donne aucun avantage.$X$$X$

La même chose s'applique lorsque vous voulez l'état de l'univers après temps. Puisque X ne peut pas décider s'il s'arrêtera dans t temps ou pas dans t temps (même argument), alors il le laissera à l'univers de le faire. Essayer de simuler l'univers en le faisant, ne peut pas réduire le temps que vous prendrez pour décider. Et si décider à quoi ressemblera l'univers en t temps prend plus que t, alors la simulation divergera (car t va à l'infini).$t$$X$$t$$t$$t$$t$$t$

Cela conduit à la conclusion que seul un simulateur utile qui décide à quoi ressemblera l'univers en temps doit prendre exactement t temps, c'est-à-dire en laissant fonctionner l'univers. Ce simulateur est alors bien le simulateur trivial.$t$$t$

Je suppose que nous pourrions essayer de voir cela comme un problème de modélisation : comment reformuler la question pour qu'elle devienne informatique et non physique? Je vais essayer de donner un exemple simple et concret de la façon dont nous pourrions essayer de faire cela, pour commencer ...

Remplaçons "l'univers" par quelque chose de très discret et simple (et fini!). Disons que notre univers est un automate cellulaire fini. En particulier, le monde entier est une grille n × n .$W$$n \times n$

Supposons que la configuration initiale du monde soit arbitraire. Maintenant, la question semble être la suivante: peut-on choisir un sous-ensemble strict C de W ("ordinateur"), et un état initial de C , qui remplissent les conditions suivantes:$W$$C$$W$$C$

• Nous ne changeons pas l'état initial de . (Autrement dit, nous "construisons simplement notre ordinateur C ", sans altérer le monde extérieur.)$W \setminus C$$C$

• Ensuite, nous pouvons exécuter un nombre quelconque d'étapes de l'automate cellulaire (le monde entier , y compris C et toutes les interactions entre W ∖ C et C ).$W$$C$$W \setminus C$$C$

• On peut lire l'état actuel du monde par simple inspection C . (C'est-à-dire que C doit être une "simulation" de W. Notez que nous devons être capables de lire l'état de W entier , pas seulement W ∖ C. Dans un sens, C doit être capable de simuler à la fois son extérieur et son intérieur !)$W$$C$$C$$W$$W$$W \setminus C$$C$

Maintenant, est-ce faisable? Il peut être tentant d'utiliser un argument de comptage (il y a plus d'états dans que dans C ) et de dire que c'est impossible. Mais ce n'est pas nécessairement le cas!$W$$C$

Supposons que notre automate cellulaire soit totaliste . Alors ce que nous pouvons faire, c'est simplement que soit la moitié droite de notre grille W , et que la configuration initiale de C soit une image miroir de W ∖ C , de sorte que tout soit symétrique. C'est ça.$C$$W$$C$$W \setminus C$

Démarrez l'automate et voyez ce qui se passe. L'état actuel de sera toujours égal à l'état de C + son image miroir. Autrement dit, une simple inspection de C suffit pour déterminer quel est l'état de W entier .$W$$C$$C$$W$

(Bien sûr, ici, l'ordinateur interagit avec et affecte l'état futur de W ∖ C. Mais c'est ce qui se passe dans le monde réel aussi.)$W$$W \setminus C$

Maintenant, il pourrait être intéressant de voir s'il existe une réponse non triviale à cette question. Par exemple, quelles autorités de certification admettent des ordinateurs dont la taille est inférieure à la moitié de ?$W$

Voici une preuve simple (non formelle). Disons que c'est l'année 2115 et j'ai un ordinateur vieux de 100 ans que j'appellerai Mac et un supercalculateur de pointe appelé Dieu. Dieu peut facilement simuler et prédire Mac, jusqu'à ce que je fasse ce qui suit:

Tout d'abord, j'attache une webcam à Mac et la pointe vers l'écran de Dieu. Ensuite, je lance sur Mac un programme qui, dans une boucle infinie, stocke chaque numéro détecté dans l'écran de Dieu et génère et affiche un numéro qui ne figure pas dans la liste des numéros stockés. Enfin, je demande à Dieu de me montrer le numéro que Mac va montrer dans une minute. Quel que soit le nombre que Dieu montre, Mac en produira et en montrera un autre, donc Dieu ne pourra pas donner une réponse correcte.

Cela équivaut au fait que si un supercalculateur me prédit, quoi qu'elle me dise que je ferai, je pourrai faire le contraire (comme dans le commentaire de Mark ). En outre, cela est valable quel que soit le processus utilisé par le supercalculateur pour prédire l'avenir (simulation, voyage vers le futur et retour, demande à un oracle, etc.).

Un ordinateur fini ne peut pas se simuler, contrairement à une machine Turing qui a une bande infinie et peut simuler n'importe quelle autre machine Turing. Il est cependant possible de simuler n'importe quel ordinateur sur un ordinateur similaire, mais vous avez besoin d'un peu plus de mémoire que celui "simulé" (comme dans une machine virtuelle): http://meaningofstuff.blogspot.com/2016/03/ can-computer-or-human-simulate-yourself.html