[C0reValuE]

Hey
Also ich muss für die Schule (13. Klasse) ein Referat über die Persistente Turingmaschine machen.
In diesem Referat enthalten sein soll folgendes:
Was ist es?
Unterschiede zur normalen Turingmaschine?
Wie funktioniert die persistente Turingmaschine?
Erklärung an einem Beispiel.
Habe in Google gewühlt und jegliche erdenkliche Kombination an Suchbergriffen durchprobiert. Das einzige was ich fand:
- nichtdeterministische 3-Band Turingmaschine (input, work, output)
- Erklärung was Persistenz in dem Zusammenhang heißt
- hat ein "Gedächtnis"
Da ich damit wohl kaum den Anspruch eines 20 Minuten Referates erfüllen kann habe ich meinen Leher angesprochen, dem mein Problem offenkundig egal gewesen zu sein scheint und mich lediglich auf englischsprachige PDF Dateien die auch bei google zu finden sind verwies. Er fügte noch hinzu, dass der Mathematische Aspekt nicht so wichtig sei und dass wir wenn es zu Mathematisch wird uns nicht damit rumschlagen müssen.
Das Problem ist, dass es in den PDF's entweder zu Mathematisch wird und ich nichts verstehe, ich im allgemeinen nichts verstehe oder die Informationen genau so karg wie im Deutschen sind.
Hat vielleicht zufällig jemand genau die selbe Aufgabe gehabt und das Referat noch irgendwo rumliegen oder kann mir wer mit Informationen weiterhelfen?

lg

[blood_warrior]

Ich hoffe du musstest das Referat noch nicht halten. Schüler machen so was ja immer relativ kurzfristig
Eine persistente Turingmaschine ist ein erweitertes Turingmaschinenmodell. Die Grundzüge hast du ja schon dargestellt. (Liest sich ein wenig wie der Wikipedia Artikel ^^) Im Gegensatz zur normalen Turingmaschine hat diese die drei von dir beschriebenen Bänder. Auf dem Eingabeband wird nur gelesen (das nennt sich Offline-Turingmaschine), auf dem Arbeitsband darf gelesen und geschrieben werden und auf dem Ausgabeband steht am Ende der Berechnung das Ergebnis. In der Regel 1 oder 0.
Prinzipiell braucht man dieses Modell nicht. Jede Mehrbandmaschine kann durch eine Einbandmaschine simuliert werden. Das Band dieser Maschine hat mehrere Spuren. Deshalb spricht man von einer Mehrspurmaschine. Das Band hat doppelt so viele Spuren wie die Mehrbandmaschine Bänder hat. In deinem Fall also 6. Auf der ersten Spur steht die Eingabe vom ersten Band. Auf der zweiten Spur wird die Kopfposition des des LSK vom ersten Band gespeichert. Das Feld wird zum Beispiel mit einem * oder einer # markiert. Auf der dritten Spur steht dann der Inhalt des zweiten Bandes usw.
Die Mehrbandmaschinen sind bei Komplexitätsbetrachtungen interessant, weil die Schritte auf dem Eingabeband nicht mitgezählt werden.
Als Beispiel kannst du gut die Erkennung der Sprache wcw nehmen. Das geht auch mit einer normalen Turingmaschine, aber nicht so schön. Zuerst wird das erste w auf das Arbeitsband kopiert. Erreicht man auf dem Eingabeband das c, läuft man auf dem Arbeitsband an den Anfang des Wortes zurück. Dann wird simultan über das w auf dem Arbeitsband und dem w auf dem Eingabeband gelaufen. Wenn am Ende w=w, dann kann eine 1 auf das Ausgabeband geschrieben werden. Falls irgendwo eine Ungleichheit auftaucht, dann kann eine 0 auf das Ausgabeband geschrieben werden. Hier wird sich die Eingabe wcw gemerkt ("Gedächtnis").
Ich hoffe das hilft dir weiter. Damit solltest du 20 min. locker voll kriegen. Im Zweifelsfall frisst das Beispiel enorm viel Zeit ^^