Zu dieser Karteikarte gibt es einen kompletten Satz an Karteikarten. Kostenlos!
69
Korrektheit
durch Dominos Teil 1
![](/pool/data/tex/0dcbc3a9325d287f9dc54af8a8170b0d.gif)
1.) M hält auf w => ![](/pool/data/tex/4178344d8d4c1a49a905c06467e4a223.gif)
Dann entspricht die Rechnung von M einer endlichen Konfigurationsfolge:
mit
Start- und
Endkonfiguration im Zustand ![](/pool/data/tex/30edc55565b06d9a34b636a00ff32208.gif)
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 ![](/pool/data/tex/bfe64bd7239fbe28b03e073bc5fff42e.gif)
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:![](/pool/data/tex/8dc7dac91600f70763b604313439e497.gif)
Wenn M auf w hält gilt also![](/pool/data/tex/4178344d8d4c1a49a905c06467e4a223.gif)
![](/pool/data/tex/4178344d8d4c1a49a905c06467e4a223.gif)
Dann entspricht die Rechnung von M einer endlichen Konfigurationsfolge:
![](/pool/data/tex/16b35eb1777ad72cd54a657ff0157567.gif)
![](/pool/data/tex/3a3a31c01221cd0fa25152cb1c38f56c.gif)
![](/pool/data/tex/2d748fa42abdf5d8d84eb3beac40535c.gif)
![](/pool/data/tex/30edc55565b06d9a34b636a00ff32208.gif)
Man kann nun nach und nach Kopier- und Überführungsdominos legen, sodass der untere String die vollständige Konfigurationsfolge von M enthält
![](/pool/data/tex/6fc675aee097a488b776f610f893123a.gif)
![](/pool/data/tex/bfe64bd7239fbe28b03e073bc5fff42e.gif)
Durch Hinzufügen der Löschdominos kann Rückstand des unteren ausgeglichen werden. Danach sind sie identisch bis auf
![](/pool/data/tex/1da69fc07e76cc7ba73cad951a2ca649.gif)
Durch hinzufügen des Abschlussdominos sind sie identisch:
![](/pool/data/tex/8dc7dac91600f70763b604313439e497.gif)
Wenn M auf w hält gilt also
![](/pool/data/tex/4178344d8d4c1a49a905c06467e4a223.gif)