Prüfungsprotokoll 1680 - Theorie der Berechenbarkeit

Datum 4.11.02

Dauer: ca 25 min.

Prüfer: Prof Weihrauch

Note: 1.0

Themengebiete

Definition rekursiver Mengen

Definition rekursiv aufzählbarer Mengen (und sämtliche äquivalente Def.)

Mengen, die ra und nicht rekursiv sind

Definition von simplen und creativen Mengen

Sind simple Mengen reduzierbar auf alle anderen ra Mengen?

Hierbei hat sich dann noch im Gespräch die Überleitung zur Äquivalenz zwischen K isomorph zu A ó A creativ und daraus der Zusammenhang zu M Vollständigkeit, etc.. (Lemma..??? ) ergeben.

Bei simplen Mengen wurde Beweis zu Nicht-Rekursivität und Zylindrifikation angesprochen.

Begriff der Reduzierbarkeit/Vergleichbarkeit von Mengen

Definition m-reduzierbar

Rekursionssatz: beide Versionen (Fixpunktsatz und uniforme Version, bei letzterem besonders der Zusammenhang mit fastvollständigen Numerierungen; für welche i gilt die uniforme Version)

Satz von Rice und verallgemeinertes Rice Theorem (letzteres nur am Rande )

Überleitung zu ra Mengen in der Logik, (vollständige Beweissysteme nur für ra Mengen, Unvollständigkeit fuer L-a-t , aus ra Menge von wahren Formeln können iterativ neue wahre Formeln erzeugt werden , die nicht aus dem ursprünglichen Axiomensystem herleitbar und in diesem nicht beweisbar sind,

Überleitung zu produktiven Mengen

Definition.. (auch hier wieder genauestens auf sämtliche Quantoren geachtet!)

Definitionen Turing und TT Reduzierbarkeit,

Erläutern der Arbeitsweise einer Orakel Maschine (wieviele Fragen gestellt werden und in welchem Fall diese schon von vorneherein feststehen )

Arithmetische Mengen - Definition von M

Charakterisierung von Sigma/Pi n über Quantoren Darstellung

Beispiele für Mengen Sigma1 , Pi2...

Wie ergibt sich Pi-n aus Sigma-n (Komplementbildung ) ?

Welche Teilmengen von N sind nicht arithmetisch ?

Prof. Weihrauch ist als Prüfer uneingeschränkt zu empfehlen. Die vorhandenen Prüfungsprotokolle sind eine optimale Prüfungsvorbereitung; da sie die Themengebiete nahezu vollständig abdecken. Auch wenn ich die Fragen weder in Reihenfolge noch in Formulierung nicht mehr exakt wiedergeben kann, da sie sich immer aus dem Zusammenhang ergeben haben, sollten sie im Wesentlichen den Prüfungsverlauf wiederspiegeln.

Die Fragen zu Zylindrifikaton wurden im übrigen nicht weiter vertieft (' das habe ich schließlich noch nie in einer Prüfung gefragt') , dagegen wird unweigerlich nachgehakt, wenn bei (einigen) Definitionen nicht genauestens auf die Quantoren /Ausdrucksweise/partiell-total etc.. geachtet wird .