f1 (1^n01^m) = 1^| m-n |Turing Maschinenkonstruktion 0 und 1
Entwurf eine Turingmaschine, die die Funktion (Übergangsdiagramm)
wie verfolgen die 0 in der Mitte berechnet? Ich habe versucht, es zu tun, aber kann es nicht herausfinden
Ich nehme an, Sie wollen das Band Alphabet nur aus 0, 1 und - (leer) bestehen. Unsere Strategie hier ist eine fruchtbare, wenn wir mit Turing-Einbandmaschinen arbeiten: Wir werden in der Mitte um die 0 hin- und herpendeln und dabei 1er absuchen, wenn wir sie finden. Wir werden fortfahren, bis wir 1 s ausgehen und eine Leerstelle erreichen. Zu diesem Zeitpunkt bleibt nur noch 1^| m-n | auf dem Band sowie n + m + 1- | m-n | Nullen. Schließlich kopieren wir unser Ergebnis an den Anfang des Bandes (wenn das nicht bereits der Fall ist, d. H. Wenn m> n ist) und löschen die Nullen.
Natürlich wäre kein TM-Beispiel vollständig ohne ein Beispiel seiner Ausführung.
-111110111- => -111110111- => -111110111-
^ ^ ^
q0 q0 q0
=> -111110111- => -111110111- => -111110111-
^ ^ ^
q0 q0 q0
=> -111110111- => -111110011- => -111110011-
^ ^ ^
q1 q2 q2
=> -111100011- => -111100011- => -111100011-
^ ^ ^
q1 q1 q1
=> -111100001- => -111100001- => -111100001-
^ ^ ^
q2 q2 q2
=> -111100001- => -111000001- => -111000001-
^ ^ ^
q1 q1 q1
=> -111000001- => -111000001- => -111000001-
^ ^ ^
q1 q1 q1
=> -111000000- => -111000000- => -111000000-
^ ^ ^
q2 q2 q2
=> -111000000- => -111000000- => -111000000-
^ ^ ^
q2 q2 q2
=> -110000000- => -110000000- => -110000000-
^ ^ ^
q1 q1 q1
=> -110000000- => -110000000- => -110000000-
^ ^ ^
q1 q1 q1
=> -110000000- => -110000000- => -11000000--
^ ^ ^
q1 q3 q3
=> -1100000--- => -110000---- => -11000-----
^ ^ ^
q1 q3 q3
=> -1100------ => -110------- => -11--------
^ ^ ^
q1 q3 q3
=> -11--------
^
halt_accept