Turingmaschine Bonusklausur

Question

Hi zusammen,

ich habe eine Frage zur Turingmaschinen Aufgabe in der Bonusklausur. Ich habe bis jetzt immer noch nicht verstanden, was passiert wenn zwei unterschiedliche Zustände beim einlesen von 0 im Zustand s0 erreicht werden können. Gibt es hier eine Parallelausführung oder kann schlichtweg beides auftreten? Da das auch weder im Übungsbuch noch im Tut noch im extra Übungsblatt vorkam habe ich mich hier sehr aufgeschmissen gefühlt und finde es sehr schade, dass ich deswegen durch den Bonus gerasselt bin.

Nichts desto trotz würde ich das gerne für die Klausur verstehen.

Viele Grüße und vielen Dank für eine Antwort

Answer 1

Hallo,

wenn es zwei oder mehr Möglichkeiten gibt, dann kann man einfach entscheiden, welches zuerst ausgeführt werden sollte (oder die Maschine, es wird nicht parallel sondern sequentiell ausgeführt). Führt der Weg in eine Sackgasse oder zur nicht Akzeptanz des Wortes, dann muss der andere Weg/Zustand ausprobiert werden. Wenn ein Wort mit dem eingeschlagenen Weg funktioniert, dann muss man den anderen nicht überprüfen. Es können also beide Zustände auftreten. Es ist also eine nichtdeterministische Turingmaschine.

Ich hoffe, jetzt ist es klarer, wenn nicht, frage gerne noch einmal nach.

Viele Güße
Anne (Tutorin)