Unendliche Berechnungen in endlicher Zeit

Dies ist wahrscheinlich ein dummer Gedanke, aber nehmen wir an einen Computer, der eine unendliche Folge von Berechnungen und nehme an, die so programmiert ist Berechnung dauert Sekunden. Dann kann dieser Computer unendlich viele Berechnungen in endlicher Zeit durchführen. $i^\text{th}$ $1/2^i$

Warum ist das unmöglich? Gibt es eine Untergrenze dafür, wie lange es dauert, eine nicht triviale Berechnung durchzuführen?

computability computation-models dsaxton
quelle

Verwandtes Konzept, unendliche Berechnungen mit endlicher Energie: Dysons ewige Intelligenz .

Peter

Antworten:

Diese "Art" von Computer ist als Zeno-Maschine bekannt . Das Rechenmodell fällt in eine Kategorie namens Hypercomputation . Hypercomputational-Modelle sind mathematische Abstraktionen und aufgrund ihrer Funktionsweise physikalisch nicht möglich.

Nehmen Sie zum Beispiel Ihre Zeno-Maschine. Wenn wir uns die Zeno-Maschine als Rechenmaschine jeglicher Art vorstellen, spielt es keine Rolle, ob sie einen Abakus oder eine integrierte Schaltung verwendet. Angenommen, die von der Maschine verwendeten Programmdaten werden von einem unendlich langen Symbolband (genau wie bei einer Turing-Maschine) eingespeist.

Natürlich wissen wir aus der Mathematik, dass:

$\frac{1}{2}+\frac{1}{4}+\frac{1}{8}... = \sum_{n=1}^{\infty}(\frac{1}{2})^n$

was wir sagen, ist gleich . Daher sollte die Berechnung in 1 Sekunde abgeschlossen sein, da die Summe absolut konvergiert. $1$

Aber diese Konvergenz hängt natürlich davon ab, dass ins Unendliche geht (und diese erreicht). Im physikalischen Sinne bedeutet dies, dass der "Lesekopf" der Rechenmaschine mit zunehmender Zeit, die für jede Berechnung benötigt wird, immer schneller entlang der Symbole auf dem Band zippen muss. Irgendwann wird diese Geschwindigkeit die Lichtgeschwindigkeit überschreiten. $n$

Wenn Sie also Ihre zweite Frage beantworten, liegt die absolut niedrigstmögliche Grenze für eine Berechnung wahrscheinlich in der Größenordnung der Planck-Zeit, da die Lichtgeschwindigkeit der primäre begrenzende Faktor in theoretischen, aber physikalisch plausiblen Berechnungsmodellen ist.

Theorie von allem
quelle

2^{256}

$2^{256}$

Beendet dieses Programm: 10: GOTO 10 auf der Zeno-Maschine?

Cano64

Einfacher ausgedrückt setzt die Mathematik voraus, dass eine "Berechnung" im Umfang unendlich teilbar ist. Dies ist jedoch bei keiner physischen Maschine der Fall, da Sie schließlich einen Punkt erreichen, an dem Sie die kleinste Arbeitseinheit erreicht haben, die die Maschine ausführen kann. Es ist nicht möglich, die Berechnung nach diesem Punkt weiter zu unterteilen, obwohl die Mathematik dies zulässt. Mit anderen Worten, die Maschine bricht aus, lange bevor Sie sich dem Ende der unendlichen Reihe von Berechnungen nähern. Irgendwann nimmt die Zeit pro Berechnung nicht mehr ab und Sie benötigen unendlich viel Zeit.

Uhr

@ Cano64 Das glaube ich nicht. Ich glaube, das Kriterium für die Entscheidbarkeit bei der Hyperberechnung ist, dass die Zeitsumme der Berechnung absolut konvergiert.

Theorie von allem

Die Zeit, die für eine primitive Berechnung benötigt wird, ist durch die Lichtgeschwindigkeit und die Größe der Atome begrenzt, soweit wir die Physik an diesem Tag, dem 15. September 2015, verstehen.

Die Recheneinheit muss aus etwas von einer Größe ungleich Null (Atomen) aufgebaut sein, und damit die Berechnung funktioniert, muss Elektrizität oder Licht darüber zippen, was durch die Zeit begrenzt wird, die Licht benötigt, um über das Nicht zu zippen -zero Abstand.

Dave Clarke
quelle

Ein konkretes Beispiel in der jüngeren Wissenschaftsgeschichte, das Grenzen überschreitet, ist der riesige Magnetowiderstand , eine mit dem Nobelpreis ausgezeichnete Entdeckung, die die Datendichte auf Festplatten ermöglichte, die bisher für unmöglich gehalten wurden. Es gibt viele, viele mehr, wenn Sie zurückgehen; Versuchen Sie, einer Person ab 1500 n. Chr. die Möglichkeit eines "Smartphones" zu erklären. (Sie verbrennen dich vielleicht nur als Hexe, also sei vorsichtig.) Ich denke, wir sollten nicht davon ausgehen, dass unsere derzeitigen Kenntnisse der Physik harte Grenzen für das Mögliche setzen.

Raphael

-1

$\Sigma_{n=1}^\infty (\frac{1}{2})^n$ $1$

$\frac{1}{2}$ $\frac{1}{4}$ $\frac{3}{4}$

$c_1$ $c_1$

Bearbeiten : Wie von @aroth bemerkt, geht diese Analogie davon aus, dass wir Wasser für immer teilen können; dass es kein kleinstes unteilbares Atom gibt. Dies wirft den interessanten (meiner Meinung nach) Punkt auf, dass wir auch davon ausgehen müssen, dass die Zeit willkürlich teilbar ist, damit die Berechnung in endlicher Zeit abgeschlossen werden kann.

epa095
quelle

"und genauso klar haben Sie immer mehr Wasser im blauen Eimer zum Übergießen" - Nicht unbedingt. Mit einem ausreichend präzisen Gießgerät erreichen Sie schließlich einen Punkt, an dem sich 2 Wassermoleküle im blauen Eimer befinden. Dann 1 Molekül. Dann gießt du entweder das letzte Molekül ein oder nicht. Oder Sie zerlegen es in seine Basisatome, aber dann ist es kein Wasser mehr (oder bei STP gießbar). Der Punkt ist, dass Sie bis zum letzten Wassermolekül kommen, bevor Sie das Ende der unendlichen Reihe erreichen, sodass sich nicht "immer" Wasser im blauen Eimer befindet.

aroth

@aroth: Ja, wahr, damit die Analogie funktioniert, muss man sich Wasser als zufriedenstellende "Dichte" vorstellen, eine Art "immer Teilbarkeit". Ihr Punkt ist interessant, da er etwas Wichtiges hervorhebt; Damit die Berechnung in endlicher Zeit abgeschlossen werden kann, muss die Zeit auch dicht / immer teilbar sein. Wenn es eine kürzeste Zeitspanne gibt, eine nicht teilbare atomare Zeiteinheit, dauert die unendliche Berechnung unendlich lange (oder jede Berechnung darf nach einem bestimmten Zeitpunkt keine Zeit mehr dauern).

epa095

\sum_{i = 1}^{\infty} 2^{- i}

$\sum_{i=1}^\infty 2^{-i}$

2^{- i}

$2^{-i}$

@ david-richerby: Wird das Problem nicht auf eine andere Art und Weise wiederholt, um es einfacher zu machen, darüber nachzudenken, genau das , was es bedeutet, Intuition zu vermitteln? Beachten Sie auch , dass Sie auch das Problem Neuformulierung von Menge an Zeit , um die Summe der rationalen Zahlen. Ein (extrem) kurzer Schritt ja, aber dennoch ein Restating. Wenn Sie über die Konvergenz von Summen rationaler Zahlen Bescheid wissen, erleichtert diese Anpassung das Verständnis, aber für einige bin ich sicher, dass es einfacher ist, sie in Bezug auf Wasser zu verstehen. Zumindest habe ich zuerst verstanden, warum einige unendliche Summen konvergierten und andere nicht.

epa095

@ epa095 Um Intuition zu vermitteln, muss eine unbekannte Situation anhand einer vertrauten Situation erklärt und die Vertrautheit mit einer Situation genutzt werden, um das Verständnis der anderen zu erleichtern. Sie tun das nicht: Sie versuchen, eine ungewohnte Situation (Berechnung einer unendlichen, konvergenten Summe) durch eine andere zu erklären (Eimer mit unendlich teilbarem Wasser mit perfekter Genauigkeit einschenken). Leute, die über die Konvergenz von Summen Bescheid wissen, brauchen die Analogie nicht; Für Leute, die nichts über die Konvergenz von Summen wissen, hilft es nicht, "rationale Zahl" in "Menge hypothetischen Wassers" umzubenennen.

David Richerby