Beschleunigte Maschine/Gedankenexperiment/Aufgabe

Führe folgendes Gedankenexperiment durch: Es sei eine Maschine gegeben, die eine Aussage (eine Vermutung) über die natürlichen Zahlen nach und nach überprüft. Wenn sie alle Zahlen überprüft hätte, stünde die Antwort fest, doch da die Maschine Schritt für Schritt arbeitet, hat sie zu jedem Zeitpunkt immer nur eine endliche Teilmenge der natürlichen Zahlen überprüft und kann so, wenn die Aussage wahr ist, keinen Beweis für die Aussage liefern.

Im Allgemeinen braucht die Rechenmaschine für große Zahlen länger. Die Maschine wird jetzt beschleunigt, sodass sie für große Zahlen immer weniger Zeit braucht.

Die Maschine wird so beschleunigt, dass sie für die Überprüfung der ersten Zahl (also ${}1$) ${}{\frac {1}{2}}$ Sekunden braucht, für die Überprüfung der zweiten Zahl ${}{\frac {1}{4}}$ Sekunden, für die Überprüfung der dritten Zahl ${}{\frac {1}{8}}$ Sekunden. Für die Überprüfung der ${}n$-ten Zahl benötigt die Maschine also genau ${}\left({\frac {1}{2}}\right)^{n}$ Sekunden. Damit ist die Gesamtlaufzeit der Maschine

${\frac {1}{2}}+\left({\frac {1}{2}}\right)^{2}+\left({\frac {1}{2}}\right)^{3}+\ldots .$

Diese Summe ist wohldefiniert, und zwar gleich ${}1$ (im Zweiersystem ist es die Zahl ${}0,111111111\ldots$, deren Wert ${}1$ ist). Nach einer Sekunde hat also die Maschine die unendlich vielen Zahlen durchgearbeitet und überprüft, und damit die Aussage bewiesen oder widerlegt.

Eine Lösung erstellen