Zenomaschine
Die Zenomaschine bezeichnet in der Berechenbarkeitstheorie eine fiktive Maschine, die in endlicher Zeit beliebig viele Berechnungsschritte ausführen kann. Sie stellt ein Beispiel für eine Leistungskraft jenseits der Turing-Berechenbarkeit dar. Der Church-Turing-These folgend kann diese Maschine in keiner Weise praktisch realisiert werden.
Die Zenomaschine ist zunächst wie eine Turingmaschine aufgebaut. Sie erreicht ihre besondere Leistungskraft, indem sie in jedem Schritt die Geschwindigkeit ihrer Berechnung verdoppelt. Benötigt sie also eine Minute für den ersten Schritt, dann dauert der zweite nur 30 Sekunden usw. Der geometrischen Folge der Schrittdauern entsprechend ist nach zwei Minuten jede Berechnung erledigt, die eine endliche Zahl an Schritte erfordert.
Hermann Weyl schlug Zenomaschinen erstmals 1927 vor. Ihr Name bezieht sich auf ähnlich gelagerte Paradoxien des Zeno von Elea.
Zenomaschinen und Berechenbarkeit
Zenomaschinen können einige nicht Turing-berechenbare Funktionen realisieren. Zum Beispiel kann das Halteproblem für Turingmaschinen mit folgendem Verfahren gelöst werden:
Schreibe eine 0 auf die erste Position des Ausgabebands
Wiederhole in einer Schleife:
Simuliere einen (weiteren) Schritt der auf dem Eingabeband gegebenen Turingmaschine
Wenn die simulierte Turingmaschine angehalten hat, schreibe eine 1 auf die erste Position des Ausgabebands und beende die Schleife
Wie oben angegeben, findet man nach zwei Minuten das Ergebnis auf dem Ausgabeband.
Anwendungen
Über die Berechenbarkeitstheorie hinaus ist die Zenomaschine zusammen mit der Church-Turing-These stets von Interesse, wenn geometrisch beschleunigte Prozesse angenommen werden, z. B.
- der Omegapunkt nach de Chardin und Tipler
- Kurzweils Gesetz des sich beschleunigenden Nutzens
Literatur
- Petrus H. Potgieter: Zeno machines and hypercomputation. In: Theoretical Computer Science. 358, Nr. 1, 31. Juli 2006, S. 23–33. doi:10.1016/j.tcs.2005.11.040.