Korrektheitsbeweis für Turingmaschine |
22.03.2014, 17:15 | Auf diesen Beitrag antworten » |
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? |
|
|