CoboCards App FAQ & Wünsche Feedback
Sprache: Deutsch Sprache
Kostenlos registrieren  Login

Zu dieser Karteikarte gibt es einen kompletten Satz an Karteikarten. Kostenlos!

Alle Oberthemen / Mathematik / Berechenbarkeit / Berechenbarkeit I
69
Korrektheit durch Dominos Teil 1
1.) 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
Neuer Kommentar
Karteninfo:
Autor: hemag
Oberthema: Mathematik
Thema: Berechenbarkeit
Veröffentlicht: 16.03.2010

Abbrechen
E-Mail

Passwort

Login    

Passwort vergessen?
Deutsch  English