Emil Leon Post verdanken wir eines der ersten unentscheidbaren Probleme, das nicht vordergr[ndig mit Bewechnung zu tun hat: das Postsche Korrespondenzproblem (international mit PCP abgekürzt). Es gleicht einem einfachen Dominospiel, aber es hat es in sich. In diesem Video sehen wir dazu ein paar Beispiele (siehe auch Literaturempfehlung unten) und wir beweisen, dass das PCP wirklich Turing-mächtig ist.
► Playliste für diesen Videokurs: • Theoretische Informati...
► Vorlesungsfolien zum Download: iccl.inf.tu-dr... (5. Vorlesung)
► Aktuelle und frühere Versionen der Vorlesung: iccl.inf.tu-dr...
► Fehler gefunden? Issues melden auf github: github.com/kno...
Literatur:
► Richard J. Lorentz: "Creating Difficult Instances of the Post Correspondence Problem." Computers and Games 2000: 214--228
► John J. O'Connor, Edmund F. Robertson: "Emil Leon Post." MacTutor History of Mathematics archive, University of St Andrews. www-history.mcs...
Негізгі бет Das Postsche Korrespondenzproblem (PCP)
Пікірлер: 1