This flashcard is just one of a free flashcard set. See all flashcards!
70
Korrektheit 
durch Dominos Teil 2
durch Dominos Teil 2M hält nicht auf w => 
Nehme zum Widerspruch an, dass M nicht auf w hält, aber
.
Nehme also an, dass eine korrespondierende Folge existiert.
1.) Mit Kopier- und Übergangsdominos entsteht bei Einhaltung der Übereinstimmung des oberen und unteren Strings die Konfigurationsfolge von M auf w. (Der obere String folgt dabei dem unteren String)
2.) Irgendwann muss auch der Abschluss- oder ein Löschdomino vorkommen. Diese enthalten jedoch im oberen Wort den Zustand
. Das Hinzufügen dieses Dominos verletzt die Übereinstimmung der beiden Strings, da im unteren String nie der Stoppzustand erreicht wird, da die Rechnung nicht terminiert. (Widerspruch zur Annahme, dass eine korrespondierende Folge existiert.)
Nehme zum Widerspruch an, dass M nicht auf w hält, aber
.Nehme also an, dass eine korrespondierende Folge existiert.
1.) Mit Kopier- und Übergangsdominos entsteht bei Einhaltung der Übereinstimmung des oberen und unteren Strings die Konfigurationsfolge von M auf w. (Der obere String folgt dabei dem unteren String)
2.) Irgendwann muss auch der Abschluss- oder ein Löschdomino vorkommen. Diese enthalten jedoch im oberen Wort den Zustand
. Das Hinzufügen dieses Dominos verletzt die Übereinstimmung der beiden Strings, da im unteren String nie der Stoppzustand erreicht wird, da die Rechnung nicht terminiert. (Widerspruch zur Annahme, dass eine korrespondierende Folge existiert.)