Zenomaschine - LinkFang.de





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.

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.

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 .

Kategorien: Keine Kategorien vorhanden!

Quelle: Wikipedia - http://de.wikipedia.org/wiki/Zenomaschine (Vollständige Liste der Autoren des Textes [Versionsgeschichte])    Lizenz: CC-by-sa-3.0

Änderungen: Alle Bilder mit den meisten Bildunterschriften wurden entfernt. Ebenso alle zu nicht-existierenden Artikeln/Kategorien gehenden internen Wikipedia-Links (Bsp. Portal-Links, Redlinks, Bearbeiten-Links). Entfernung von Navigationsframes, Geo & Normdaten, Mediadateien, gesprochene Versionen, z.T. ID&Class-Namen, Style von Div-Containern, Metadaten, Vorlagen, wie lesenwerte Artikel. Ansonsten sind keine Inhaltsänderungen vorgenommen worden. Weiterhin kann es durch die maschinelle Bearbeitung des Inhalts zu Fehlern gerade in der Darstellung kommen. Darum würden wir jeden Besucher unserer Seite darum bitten uns diese Fehler über den Support mittels einer Nachricht mit Link zu melden. Vielen Dank!

Stand der Informationen: August 201& - Wichtiger Hinweis: Da die Inhalte maschinell von Wikipedia übernommen wurden, ist eine manuelle Überprüfung nicht möglich. Somit garantiert LinkFang.de nicht die Richtigkeit und Aktualität der übernommenen Inhalte. Sollten die Informationen mittlerweile fehlerhaft sein, bitten wir Sie darum uns per Support oder E-Mail zu kontaktieren. Wir werden uns dann innerhalb von spätestens 10 Tagen um Ihr Anliegen kümmern. Auch ohne Anliegen erfolgt mindestens alle drei Monate ein Update der gesamten Inhalte.