| 0664jester |
Korrektheitsbeweis für Turingmaschine
Aus:
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag Themenstart: 2014-03-22 13:58
Hallo,
Ich habe folgende Aufgabenstellung bekommen:
Beweisen sie formal, dass die Maschine korrekt funktioniert, dh dass sie genau dann den Haltezusatand erreicht, wenn die Eingabe aus COUNT2 ist.
Einbandturingmaschine
Count2 = a^n b^n (n element von Natuerlichen Zahlen inkl 0)
Meine Turingmaschine funktioniert so, dass zuerst ein a liest und dann nach li bewegt bis zum ersten leeren feld, wo sie ein x reinschreibt. Dann bewegts sich der cursor nach rechts und liest den naechsten buchstaben. Wenn sie ein b liest dann gehts sie nach li und uebschreibt das x mit j damit sie weiss, dass sie schon mal da war.
jjj#aaabbb
ich hab da zwar einen beweis eines palindroms aber das sagt mir gar nichts
ui = x1 ... xi
vi = xi+1 ... xn
p(i) = qw -> ui qvi <-> w = ui * vi
--------------
vollstaendige Induktion
Abbruchbestimmung vi = e
-> qw -> wg
--------------
p(i) = sw -> swi <-> w = vi ° wi vi^R
vollst. Induktion (4 Faelle)
a a sawi+1 -> swi+1 <-> w = viwi+1vi^R
a b sw -> swi -> swi+1 b->a1wi+1b -> wi+1 a2 b
b a siehe Faelle a,b -> False <-> False
b b siehe Faelle a,a -> True <-> True
Schleifenabbruch:
Wi = {} (leeres Wort ist damit gemeint)
sw -> x <-> w=vi°wi°vi^R = vi°vi
-> j
Die Machine akzeptier(j) das Eingabewort genau dann wenn vi°vi erfuellt ist.
kann mir jemand helfen wie man beweist? |
