Benutzer:Cobalt pen/p/Zeno Maschine

In der Berechenbarkeitstheorie bezeichnet die Zenomaschine 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 irgendwie vollstellbaren 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.

Die Zenomachinen wurden erstmalig 1927 von Hermann Weyl vorgeschlagen. Ihr Name bezieht sich auf ähnlich gelagerte Paradoxien des Zeno von Elea.

Zenomaschinen und Berechenbarkeit

Zenomachinen 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 gegeben 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.

Das Halteproblem für Zenomaschinen ist nicht mit Zenomaschinen lösbar (Potgieter, 2006).

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.

• Dem 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. Jahrgang, Nr. 1, 31. Juli 2006, S. 23–33, doi:10.1016/j.tcs.2005.11.040. 

Kategorie:Automatentheorie Kategorie:Berechenbarkeitstheorie