BuK-Übung05

Aus ProgrammingWiki
< BuK < IIm11
Archivierte Version vom 2012-04-18T11:48:59+00:00. Aktuelle Version

Inhaltsverzeichnis

Postsches Korrrespondenzprobelm PCP

Aufgabe 1

Für K = ((001; 0)(01; 011); (01; 101); (10; 001)) gibt es eine Lösung. Die gesuchte Indexfolge heißt

(2 4 3 4 4 2 1 2 4 3 4 3 4 4 3 4 4 2 1 4 4 2 1 3 4 1 1 3 4 4 4 2 1 2 1 1 1 3 4 3 4 1 2 1 4 4 2 1 4 1 1 3 4 1 1 3 1 1 3 1 2 1 4 1 1 3)

Uberprüfen Sie die angegebene Lösung per Hand.

Aufgabe 2

Entwickeln Sie eine Scheme-Prozedur (ProgrammingWiki), die bei Aufruf für eine gegebene Instanz eine Lösung des PCP findet, falls eine solche existiert und der Rechenaufwand im Rahmen bleibt.

Turing-Maschine und Churchsche These

Turing-Maschine als Akzeptator

Geben Sie Trichterbilder für den Einsatz einer TM als Akzeptator an:

  • für semi-entscheidbare Sprachen
  • für entscheidbare Sprachen

Turing-Aufzählbarkeit, Turing-Entscheidbarkeit

Definierten Sie die Begriffe Turing-aufzählbar und Turing-entscheidbar analog zur Turing-Berechenbarkeit.