Datum : 15.8.1994
Zeit : 10.00 Uhr

Dauer : 45 Minuten

Prüfer : Prof. Dr. Weihrauch

Beisitzer : Herr Schröder

Note : 2.0

1) Definition der Berechenbarkeit von Zahlenfunktionen angeben.

2) Definition m -rekursive Zahlenfunktionen angeben.

3) Hier fragte W. schon nach der Existenz nicht berechenbarer Funktionen ; was mich einigermaßen überraschte. W. stellte die Frage aber dann doch zurück (bis zum Thema Kj ).

4) Ist die Funktion f:N---->N f(x,y)=div falls x=y, 0 sonst berechenbar ? Antwort: Ja! Man kann eine Registermaschine angeben die f berechnet.

5) Definition der Wortberechenbarkeit angeben.

6) Definition der Eingabecodierung einer Bandmaschine angeben.

7) Definition der Datenmenge einer Bandmaschine angeben. Dabei d(-1),d(0),d(1) erläutern.

8) Zusammenhang zwischen Register- und Wortberechenbarkeit erläutern. Entsprechenden Satz zitieren und Diagramm zu n f=gn erläutern wobei n :N¾ >W(S ); f:N---->N; g:W(S )---->W(S ) sind.

9) Definition Numerierung

10) Definition rekursive Mengen

11) Abschlusseigenschaften (Vereinigung, Schnitt, Komplement) nennen und für das Komplement beweisen.

12) Definition rekursiv aufzählbare Mengen

13) Abschlusseigenschaften (Schnitt, Vereinigung)

14) Definition von Kj nennen und "Kj ist nicht rekursiv" beweisen.

15) Definitionen utm-Theorem; smn-Theorem sowie den Äquivalenzsatz von Rogers nennen und erläutern.

16) Definition reguläre Mengen.

17) Wie transformiert man einen gegebenen endlichen Automaten in einen regulären Ausdruck? (Lkij....).

18) Ist L={aibjck| i<=j<=k} regulär? Ist L kontextfrei?

19) Definition Pumpinglemma für kfS.

20) Wie ist die Sprache einer Kontrollturingmaschine definiert?

21) Wie ist FZEIT(F); wie ist NP definiert?

22) Zeithierarchiesatz zitieren.

Die Prüfung barg für mich einige Überraschungen. Zum Beispiel war nach meiner Kenntnis in keinem der früheren Protokolle die Frage nach dem Äquivalenzsatz von Rogers genannt. Auch hatte ich den Beweis "m -rekursiv <=> register berechenbar" fest eingeplant. Professor Weihrauch half mir über kleinere Schwächen durch gezielte Hinweise oder Neuformulierungen hinweg.

Die Prüfung verlief in einer ruhigen freundlichen Form. Herr Prof. Weihrauch ist als Prüfer auf jeden Fall zu empfehlen.

V I E L G L Ü C K ! ! !