Entscheiden Sie sich für die Familie der Turing-Maschinen, die sich bei einigen Eingaben unendlich nach rechts bewegen

  • Ich brauche Hilfe bei der Suche nach einem Algorithmus, der angesichts einer Beschreibung der Turing-Maschine $ \ langle M \ rangle $ entscheidet, ob eine Eingabe $ w $ vorhanden ist, die bei der Berechnung von $ M (w) $, der Kopf bewegt sich nur nach rechts und $ M $ bleibt nie stehen.

    14 August 2012
    Raphael
1 answer
  • Wie sieht der Zustandsgraph von $ M $ für eine Turing-Maschine $ M $ aus, für die eine solche Eingabe existiert?

    Für einige Eingaben $ w $ wird die Form $ q_0 \ leadsto q (\ leadsto q) ^ \ omega $ berechnet, deren Übergänge alle die Bewegung $ R $ (oder $ N $) haben die Bedeutung von "nur"). Daher muss der Zustandsgraph einen "$ R $ -Pfad" von $ q_0 $ zu einigen $ q $ haben, die auf einem "$ R $ -Zyklus" liegen.

    Ist dies auch ein ausreichendes Kriterium? Die Antworten auf beide Fragen führen Sie zu einem Entscheidungsverfahren.

    15 August 2012
    Raphael