StartseiteVon Bits und Bytes

Turingmaschinen und Turing-Vollständigkeit

Von / 12. Oktober 2011 / 20 Kommentare / Seite 3 von 3 / Auf einer Seite lesen
Mehr

Und wer sich jetzt fragt, wozu man Turingmaschinen überhaupt benötigt: sie sind wie gesagt ein rein hypothetisches Konzept der theoretischen Informatik, welches dazu benutzt wird, verschiedene Eigenschaften von Problemen und Programmiersprachen zu diskutieren. Aber dazu schreibe ich in einem späteren Artikel noch etwas.

1 / 2 / 3
Stichworte: ,
Mehr

Kommentare (20)

  1. #1 rolak
    Oktober 12, 2011

    So exotisch Turing-Maschinen zu sein scheinen – die Beschäftigung mit ihnen kann durchaus spaßig sein. Sich einen 5-zuständigen fleißigen Biber zu erprobieren kann suchtgefährdend sein 😉

  2. #2 Sven Türpe
    Oktober 12, 2011

    Siehe auch: https://aturingmachine.com/

  3. #3 Marcus Frenkel
    Oktober 12, 2011

    @Sven Türpe
    Netter Link, danke. Auch wenn er meiner Aussage, dass Turingmaschinen nicht umsetzbar sind, etwas widerspricht. Aber man kann ja anführen, dass das im Link keine echte Turingmaschine ist. 😉

  4. #4 Timmorn
    Oktober 12, 2011

    Das Paper zur Turingmaschine wurde übrigens ersteinmal abgelehnt – mit einer großartigen Begründung:
    https://www.fang.ece.ufl.edu/reject.html

  5. #5 Stefan W.
    Oktober 12, 2011

    wir wir wissen, wäre das Ergebnis hierfür “10”.

    Korrekturen: **wie** wir wissen wäre das Ergebnis hierfür **”1″**.

    Beim Komma bin ich mir nicht sicher. Aber weil es auch später wiederholt wird, dass das Ergebnis der Addition von 0 und 1 10 sei, wo ich immer den Eindruck hatte, dass das das Ergebnis der Addition von 1 und 1 sei, frage ich nochmal nach – vielleicht habe ich es ja nicht verstanden.

  6. #6 Sven Türpe
    Oktober 12, 2011

    Noch ein Tipp für Bücherfreunde: The Annotated Turing geht Satz für Satz durch Turings Paper und ergänzt es um Erläuterungen, Beispiele und historische Betrachtungen.

  7. #7 schlappohr
    Oktober 12, 2011

    Im Studium haben wir die ganze Berechenbarkeitstheorie anhand der “mü”-Rekursion aufgezogen. Die Klasse dieser Funktionen ist äquivalent zur Klasse der Turing-berechenbaren Funktionen, kommt aber ohne das theoretische Modell einer Maschine aus, sondern basiert auf einer handvoll (ich glaube 3 oder 4) Grundfunktionen. Irgendwie fand ich die u-Rekursivität griffiger als Turingmaschinen, aber das ist vermutlich Geschmackssache 🙂

  8. #8 Marcus Frenkel
    Oktober 12, 2011

    @Stefan W.
    Danke für den Hinweis; natürlich kommt “01” heraus und nicht “10”. Man sollte doch keine Artikel schreiben, wenn man nebenher eigentlich ganz andere Dinge macht. Ich habe es im Artikel einmal ohne weitere Markierung korrigiert (man vergebe mir), damit die Tabellen nicht ganz so wüst aussehen.

  9. #9 Stefan W.
    Oktober 13, 2011

    Ich habe es im Artikel einmal ohne weitere Markierung korrigiert (man vergebe mir),

    Keine Ursache. Flüchtigkeitsfehler gross zu dokumentieren bringt m.E. wenig.

  10. #10 BreitSide
    Oktober 13, 2011

    xxx

  11. #11 Gustav
    Oktober 14, 2011

    Das Band muß betreffs der Länge doch nur die Bedingung erfüllen, dass der Lese/Schreibkopf bei einer Berechnung nicht an das Ende stößt.

    Nur um zu zeigen, dass eine Turingmaschine eben nicht alle Probleme lösen kann, sondern nur alle Probleme einer bestimmten Klasse von berechenbare Funktionen (Turing-Berechenbarkeit), brauche ich ein endloses Band.

    Diese Probleme sind aber nur ein “Anwendungsgebiet” der Turingmaschine. Wenn ich damit nur zeigen will, dass eine Turingmaschine eine (Turing-) berechenbare Funktion lösen kann, benötige ich doch kein endloses Band (es muß nur solange sein, dass die Berechnung ungehindert ausgeführt wird).

    Oder irre ich da?

  12. #12 Gustav
    Oktober 14, 2011

    Ach ja, The LEGO Turing Machine: https://www.youtube.com/watch?v=cYw2ewoO6c4

    😉

  13. #13 rolak
    Oktober 14, 2011

    Leider in D-Land wg A-Team gesperrt, da war der militärische Geheimdienst schneller, Gustav 😉
    Da hinten gibt es die ganzen Daten und zum clip-Anschauen reicht es schon, den Hintern bedeckt zu lassen.

  14. #14 Marcus Frenkel
    Oktober 14, 2011

    @Gustav
    Im Prinzip ist das richtig – für das Lösen eines bestimmten Problems muss das Band nur so lang sein, dass das Problem “draufpasst”. Allerdings gibt es ja auch Probleme, die nicht gelöst werden können, oder deren Lösung “unendlich lange” dauert – z.B. die Berechnung von Pi. Für derartige Probleme wird ein unendlich langes Band (und unendlich viel Zeit) benötigt; möchte man zudem eine universelle Turingmaschine konstruieren, muss man auch diese Probleme berücksichtigen und benötigt daher auch dafür ein unendlich langes Band. Daher wird im Allgemeinen gleich die Aussage getroffen, dass man für Turingmaschinen “an sich” ein unendlich langes Band braucht; aber ja, für spezielle Maschinen ist natürlich kein unendlich langes notwendig.

  15. #15 7tupel
    Oktober 14, 2011

    Da fühlt man sich doch gleich wieder in die Theorie Vorlesung an der Uni zurückversetzt 😉
    Für den einen oder anderen ist es vielleicht noch interessant zu wissen, dass man ausgehend von der “normalen” Turingmaschine auch welche konstruieren kann, die mehr als eine Spur auf dem Band haben, d.h. man kann mehrere Zeichen parallel lesen/schreiben. Und natürlich noch die Mehrbandmaschinen, die mehrere Bänder und Schreib-Lese Köpfe haben. Nicht zu vergessen die nicht-deterministischen Maschinen…
    Gibt es dazu später noch einen Artikel? Denke das wäre eine interessante Erweiterung für die meisten Leser.

  16. #16 Marcus Frenkel
    Oktober 14, 2011

    @7tupel
    Wenn mir jemand eine Mail mit seinen Wünschen schreibt (so dass ich sie gut sichtbar im Posteingang belassen kann), dann kommt da bestimmt noch einmal etwas. 😉

  17. #17 Stefan W.
    Oktober 14, 2011

    Allerdings gibt es ja auch Probleme, die nicht gelöst werden können, oder deren Lösung “unendlich lange” dauert – z.B. die Berechnung von Pi.

    Interessanter aber, im Zusammenhang mit Turing, sind doch die Probleme, bei denen man vorher nicht weiß, ob sie terminieren werden. Dass die Pi-Berechnung nicht terminieren wird, dass weiß man ja vorher.

  18. #18 Marcus Frenkel
    Oktober 14, 2011

    @Stefan W.
    Richtig. Die Pi-Berechnung war jetzt auch nur ein Beispiel, wobei sie sich insofern von vielen der nicht-endenden Probleme unterscheidet, als dass immerhin bekannt ist, dass es eine Lösung gibt. Bei vielen Problemen, wo vorher nicht bekannt ist, ob sie terminieren, weiß man ja auch gar nicht, ob überhaupt eine Lösung existiert.

  19. #19 engywuck
    Oktober 14, 2011

    @Timmorn: dass der Text hinter deinem Link eine Satire ist weisst du?

  20. #20 rolak
    Oktober 14, 2011

    Verräter^^