Was sind die Grenzen der Berechnung in diesem Universum?

17

Ich verstehe, dass die Vollständigkeit von Turing unbegrenztes Gedächtnis und unbegrenzte Zeit erfordert.

Es gibt jedoch eine begrenzte Anzahl von Atomen in diesem Dienst, wodurch das Gedächtnis begrenzt wird. Zum Beispiel, obwohl irrational ist, gibt es keine Möglichkeit, mehr als eine bestimmte Anzahl von Ziffern zu speichern, selbst wenn alle Atome im Universum für diesen Zweck verwendet wurden.π

Was sind dann die Grenzen der Berechenbarkeit einer implementierten Turing-Maschine (die alle Ressourcen des Universums nutzen könnte, aber nicht mehr), basierend auf den Grenzen des Universums? Was ist die maximale Anzahl von Stellen von ? Gibt es Beiträge zu diesem Thema, die interessant zu lesen sein könnten?π

Guter Mensch
quelle
1
Möglicherweise verwandtes Thema: Kann ein Computer simuliert selbst als Teil einer simulierten Welt .
MS Dousti
7
Es gibt einen lustigen Aufsatz von Scott Aaronson dazu: scottaaronson.com/writings/finite.html
Artem Kaznatcheev
2
Die Diskussion um diese Frage könnte Sie interessieren . Yarosloav Bulatov hat einen Link zu einer populärwissenschaftlichen Version des Lloyd-Papers Peter Shor gepostet, auf den unten verwiesen wird. Leider scheint der Link jetzt nicht mehr zu funktionieren. Ich habe die Zeitung damals gelesen, aber nicht gespeichert und erinnere mich nicht an den genauen Titel.
Aaron Sterling

Antworten:

34

Seth Lloyd hat eine Arbeit zu diesem Thema. Sie benötigen Energie zum Berechnen, aber wenn Sie zu viel Energie in eine kleine Region stecken, bildet sich ein Schwarzes Loch. Dies verlangsamt die Zeit (was die Rechenzeit relativ verlängert), und jede im Inneren eines Schwarzen Lochs durchgeführte Berechnung wird verschwendet, da die Ergebnisse nicht aus dem Schwarzen Loch extrahiert und verwendet werden können. Seth berechnet die Grenzen des möglichen Rechenaufwands und zeigt, dass für einige Rechenmaße die rechenintensivste Umgebung im Universum diejenige ist, die ein Schwarzes Loch umgibt.

Peter Shor
quelle
10
@AaronRoth Ich war in einem schwarzen Loch gefangen. Jetzt angenommen.
Gute Person