BuK/IIm11/Studenten/sijeheid/ue5

Wiki-Quelltext dieser Seite.

== Mathematik vs. Informatik ==
=== Aufgabe 1 ===
Defnieren Sie je eine totale Funktion für den Vorgänger und die Halbierung einer natürlichen Zahl. Defnieren Sie außerdem eine Funktion mit $ D_f = \N \setminus \{1234, 7266281\} $.

== 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.

Lösung siehe Bild...

[[Bild:Sijeheid_2012-04-22-025.jpg]]

=== 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.