Diese Frage ist eine Fortsetzung der Frage zu DNA-Algorithmen, die Aadita Mehra gestellt hat .
In Kommentaren sagte Joe Fitzsimmons zum Teil:
Der Radius des Systems muss proportional zur Masse skaliert werden, um dies zu vermeiden. Die Rechenleistung skaliert höchstens linear in der Masse. Ihre exponentielle Maschinenmenge hat also einen exponentiellen Radius. Da Sie nicht schneller als mit Licht signalisieren können, dauert es exponentiell lange, bis ein Signal von einer Seite zur anderen gelangt. Wenn also alle Geräte zur Lösung beitragen, ist es unmöglich, das Problem in weniger als exponentiellen Schritten zu lösen Zeit.
Meine Frage besteht aus zwei Teilen.
(1) Wie lässt sich eine Aussage wie "Die Rechenleistung skaliert höchstens linear in der Masse" am besten formalisieren? Steht diese Aussage wirklich nicht zur Debatte?
(2) Angenommen, die Aussage ist wahr. Könnte die Natur jedoch bereits eine exponentielle Menge von Vorverarbeitungen durchgeführt haben, die wir nutzen könnten, beispielsweise die Schaffung von Sichtsystemen durch "Brute-Force-Randomisierung" durch die Evolution.
Ich habe eine ganze Reihe von leisen (pseudowissenschaftlichen) Antworten auf Fragen dieser Art gehört und gelesen, und ich wäre dankbar für alle Antworten, aber ich bin am meisten daran interessiert, wie (1) und (2) neu gefasst werden können in TCS Strenge.
quelle
Antworten:
Die Aussage, die ich machte, war nicht besonders gut geschrieben. Ich bezog mich auf eine Kombination des Margolus-Levitin-Theorems (das die minimale Zeit zum Bewegen zwischen zwei orthogonalen Zuständen und damit eine untere Schranke für die zum Durchführen eines Gates erforderliche Zeit angibt) und des Schwarzschild-Radius (das den minimalen Radius von angibt) ein System fester Energie, bevor es ein Schwarzes Loch bildet). Die Kombination dieser beiden führt zu einer Obergrenze für die Anzahl der Gatter, die in einem festen Raumzeitbereich ausgeführt werden können. Sie können sich dies als die maximale Anzahl von Toren pro Zeiteinheit vorstellen, die ausgeführt werden können.
Die Idee, die beiden Theoreme zu kombinieren, stammt von Seth Lloyd, der mit einem solchen Ansatz Grenzen für die Rechenleistung des Universums aufzeigt ( Link ). Er hat auch eine andere Veröffentlichung, in der er die maximale Leistung untersucht, die mit einem 1 kg schweren Computer mit einem Volumen von 1 Liter erreicht werden kann (etwas, das er den ultimativen Laptop nennt und das fast genau Ihre Frage ist). Siehe arXiv . Er erhält ein Limit von Operationen pro Sekunde für Bits. Aufgrund des endlichen Alters des Universums und der endlichen Lichtgeschwindigkeit erhalten Sie in Kombination mit Lloyd's Ergebnissen eine konstante Obergrenze für die Vorverarbeitung.1051 1031
quelle