Korrektheitsbeweis für Turingmaschine

Neue Frage »

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?
 
 
Neue Frage »
Antworten »


Verwandte Themen

Die Beliebtesten »
Die Größten »
Die Neuesten »