Entwerfen einer Turing-Maschine Zustandstabelle

Question

Sind sie alle hilfreichen Leitlinien zu beschreiben, was eine Turing-Maschine funktioniert, wenn Sie bereits über die Pseudo-Code haben für den Algorithmus?

ich einen Kurs über Komplexitätstheorie zu nehmen und es dauert eine Weile, eine Turing-Maschine zu beschreiben, die entscheiden, oder akzeptiert eine Sprache (Zustände, Übergänge, etc.), obwohl ich weiß, wie ich es in so etwas wie C-Code könnte oder sogar Montage. Ich glaube, ich habe einfach nicht genug Praxis mit Turingmaschinen (arbeitet) hatte, aber ich schätze Anregungen.

Bearbeiten

Ich will nicht einen Turing-Maschine-Simulator machen, möchte ich einige Sprache eine Turing-Maschine auf dem Papier (Alphabet, Zustände, Übergänge) beschreiben, für die Entscheidung.

Hier ist ein triviales Beispiel dafür, was ich meine, sage ich brauche eine Turing-Maschine zu schreiben, die eine Kette von 0 und 1 übergeht und ändert alle 0s darin 1s. Zum Beispiel, wenn Sie mit 11.010 auf dem Band (Eingang) beginnen hält es mit 11.111 auf dem Band (Output). Jetzt in einer Hochsprache wissen Sie, es ist so etwas wie:

Go over every character on tape
    If character is 0 change it to 1

Die Beschreibung Turing-Maschine ist informell etwas wie:

  

Sie haben zwei Zustände, q und Halt. Wann   Sie sind auf Zustand q und Sie erhalten eine 1 zu sehen, gehen   nach rechts, ohne sie zu verändern. Wenn   sehen Sie eine 0, ändern Sie ihn auf 1 und gehen Sie zu   das Recht. Wenn Sie das leere Symbol sehen   (Ende des Bandes) geht dann zum Stillstand   Zustand.

Formal haben Sie so etwas wie {q, halt} für Staaten. {((Q, 1) -> (q, 1, R)), ((q, 0) -> (q, 1, R)), ((q, #) -> (Halt, 0, L) )} für Übergänge.

Nun ist dieses Problem ist trivial, aber es gibt andere, die mehr beteiligt sind (einstellige Zahlen addieren oder eine Sprache mit der gleichen Anzahl von a, b ist, und c des erkennen). Ich konnte die Pseudo-Code für sie leicht schreiben, aber die Turing-Maschine zu schreiben ist viel anspruchsvoll (dauert eine lange Zeit) und ich frage mich, ob es einige Tipps waren, Ressourcen oder Richtlinien, die helfen, mich besser zu werden, um Probleme wie das zu lösen.

Answer 1

Hinweis: Ihre Frage sehr allgemein gehalten ist, ist daher so diese Antwort. Beachten Sie, dass ich bin alles andere als ein Experte für TMs und Dieser Ansatz wird in der Regel nicht sehr effizient (ich kann nicht einmal versprechen, es wird immer wirksam sein). Ich notiere nur einige Gedanken hier.

Ich würde vorschlagen, einen Ansatz wie diese versuchen: Nehmen Sie Ihre Pseudo-Code und reduzieren es so, dass es besteht nur aus a) boolean Variablen und b) if-Aussagen. Zum Beispiel:

if THIS_LETTER_IS("A"):
    found_an_even_number_of_A = not found_an_even_number_of_A

if THIS_LETTER_IS("Q") and previous_letter_was_X and found_an_even_number_of_A
        and not checking_for_alternative_2:
    # can't be a word of alternative 1, so check for alternative 2
    going_back_to_start_to_check_for_alternative_2 = True

if going_back_to_start_to_check_for_alternative_2:
    MOVE_TO_PREVIOUS
else:
    MOVE_TO_NEXT

if going_back_to_start_to_check_for_alternative_2 and THIS_LETTER_IS(EMPTY):
    # reached the beginning, so let's check for alternative 2
    going_back_to_start_to_check_for_alternative_2 = False
    checking_for_alternative_2 = True

Wenn Sie verschachtelte ifs haben, ersetzen Sie sie durch ands; entfernen else Blöcke von not mit:

if something:
    if something_else:
        do_a
    else:
        do_b

wird

if something and something_else:
    do_a

if something and not something_else:
    do_b

Jeder if Block soll dann enthält nur eine MOVE_TO_PREVIOUS oder MOVE_TO_NEXT, möglicherweise einen WRITE Befehl und eine beliebige Anzahl von Variablenzuweisungen.

Führen Sie alle if Klauseln, so dass jeder einzelne Ihr booleans und der aktuelle Brief wird immer geprüft, Vervielfältigen die Blöcke, wo notwendig. Beispiel:

if something and something_else:
    do_a

wird

if THIS_LETTER_IS("A") and something and something_else and something_i_dont_care_about_here:
    do_a

if THIS_LETTER_IS("A") and something and something_else and not something_i_dont_care_about_here:
    do_a

if THIS_LETTER_IS("Q") and something and something_else and something_i_dont_care_about_here:
    do_a

if THIS_LETTER_IS("Q") and something and something_else and not something_i_dont_care_about_here:
    do_a

Nun, wenn Sie n booleans und m Buchstaben, sollten Sie m * 2 ⁿ ifs. Man stelle sich vor, um die booleans in einem Bitfeld gespeichert sind, so dass jede mögliche Kombination von booleans ein repräsentiert ganze Zahl. Daher oben das wird

if THIS_LETTER_IS("A") and bitfield[0] and bitfield[1] and bitfield[2]:
    do_a

if THIS_LETTER_IS("A") and bitfield[0] and bitfield[1] and not bitfield[2]:
    do_a

# ...

, die dann wird

if THIS_LETTER_IS("A") and bitfield == 7:
    do_a

if THIS_LETTER_IS("A") and bitfield == 3:
    do_a

# ...

Dieser ganzzahlige Wert für die bitfield ist der Turing-Maschine Zustand. Der do_a Teil ist nur eine Zuordnung zu den booleans (das heißt, das Bitfeld, so ist es Ihr neuer Zustand), ein Schreibbefehl (wenn es keine ist, nur den Brief schreiben, die schon war dort) und ein Bewegungsbefehl, daher explizit ein Turing-Maschine-Übergang.

Ich hoffe, dass eine der oben genannten Sinn macht.

Answer 2

Sie benötigen ein ready-to-use-Tool, Turing-Maschine-Simulator? Es gibt ziemlich viele verfügbar . Oder eigentlich wollen Sie Ihre eigenen machen? Dies scheint eine gültige Implementierung in JavaScript zu sein: http://klickfamily.com/david/ Schule / cis119 / TuringSim.html könnte den Code analysieren und sie in C oder C ++ übersetzt ganz leicht.