This flashcard is just one of a free flashcard set. See all flashcards!
69
Korrektheit 
durch Dominos Teil 1
durch Dominos Teil 11.) M hält auf w => 
Dann entspricht die Rechnung von M einer endlichen Konfigurationsfolge:
mit 
Start- und 
Endkonfiguration im Zustand 
Man kann nun nach und nach Kopier- und Überführungsdominos legen, sodass der untere String die vollständige Konfigurationsfolge von M enthält
und der obere String ein Präfix des unteren ist 
Durch Hinzufügen der Löschdominos kann Rückstand des unteren ausgeglichen werden. Danach sind sie identisch bis auf
.
Durch hinzufügen des Abschlussdominos sind sie identisch:
Wenn M auf w hält gilt also
Dann entspricht die Rechnung von M einer endlichen Konfigurationsfolge:
mit Start- und Endkonfiguration im Zustand Man kann nun nach und nach Kopier- und Überführungsdominos legen, sodass der untere String die vollständige Konfigurationsfolge von M enthält
und der obere String ein Präfix des unteren ist Durch Hinzufügen der Löschdominos kann Rückstand des unteren ausgeglichen werden. Danach sind sie identisch bis auf
.Durch hinzufügen des Abschlussdominos sind sie identisch:
Wenn M auf w hält gilt also
