wenn es eine Registermaschine gibt, die diese Funktion berechnet,

wenn die Funktion WHILE-berechenbar ist,

wenn die Funktion m-rekursiv ist.

Wann heißt denn eine Funktion m-rekursiv?
Eine Funktion heißt m-rekursiv, genau dann wenn sie sich in endlich vielen Schritten aus der Menge Gr durch wiederholtes Anwenden der Operatoren Prk, m̃ und Sub erzeugen lässt. Prk, m̃ und Sub sind die Operatoren der primitiven Rekursion, der m-Rekursion und der Substitution. Das Aufschreiben der Menge Gr war nicht erforderlich.

Was bedeutet es, wenn wir sagen: eine Funktion "heißt" berechenbar?
Mit "... heißt berechenbar ..." meint man, dass die Funktion gemäß unserer mathematischen Definition (Registermaschine) berechenbar ist. Man kann sich leicht klar machen, dass man zu jeder Registermaschine ein ASSEMBLER- oder PASCAL-Programm angeben kann, was die Berechnung der Maschine auf einem realen Rechner nachvollzieht. Insofern kann man sagen, dass jede Register-berechenbare Funktion auch maschinell berechenbar ist. Es stellt sich die Frage, ob es maschinell berechenbare Funktionen gibt, die nicht Register-berechenbar sind. Bis heute ist es nicht gelungen, eine maschinell berechenbare Funktion anzugeben, die nicht Register-berechenbar ist. Nach der Churchschen These sind die Register-berechenbaren Funktionen genau die maschinell berechenbaren Zahlenfunktionen.

Welche Maschinenmodelle haben wir im Zusammenhang mit Wortfunktionen kennen gelernt?
Turingmaschinen und Bandmaschinen.

Wann heißt eine Wortfunktion berechenbar?
Eine Wortfunktion heißt berechenbar, genau dann wenn es eine Turingmaschine gibt, die diese Funktion berechnet.

Wir hatten also berechenbare Zahlen- und berechenbare Wortfunktionen. Gibt es da einen Zusammenhang?
Der Zusammenhang wird hergestellt durch bijektive Standardnumerierungen n : IN ® S^*. Mit einer Standardnumerierung n kann man Wörter durch Zahlen und umgekehrt Zahlen durch Wörter verschlüsseln.
Hinsichtlich der Berechenbarkeit gilt Folgendes (ich brauchte es nur für einstellige Funktionen zu zeigen):
Eine Wortfunktion g :Í S^* ® S^* ist berechenbar, genau dann wenn ihre Verschlüsselung n^-1gn :Í IN ® IN eine berechenbare Zahlenfunktion ist.

Wann heißt eine Menge A Í IN rekursiv?
Ich habe die vier im Kurs genannten Charakterisierungen aufgezählt:

Eine Menge heißt rekursiv, gdw. ihre charakteristische Funktion berechenbar ist.

Eine Menge A Í IN ist rekursiv, gdw. es eine totale berechenbare Funktion  f Î R⁽¹⁾ gibt mit A = f ^-1{0}.

Es sei A Í IN unendlich. Dann gilt: A ist rekursiv, gdw. es eine wachsende Funktion  f Î R⁽¹⁾ gibt mit A = Bild(f).  

Eine Menge A Í IN ist rekursiv, gdw. A und das Komplement IN \ A rekursiv-aufzählbar sind.

Gut, dann will ich nach der Definition von rekursiv-aufzählbar nicht mehr fragen.
Wie zeigt man denn, dass eine Menge, die rekursiv ist, auch rekursiv-aufzählbar ist?
Den Beweis sollte ich auf Maschinenebene führen. Prof. Weihrauch gab den Tipp, erst einmal zu erklären, was rekursiv bzw. rekursiv-aufzählbar auf der Ebene der Maschinen bedeutet:

Wenn eine Menge A Í IN rekursiv ist, gibt es eine Registermaschine, die für jedes x Î IN die Antwort "ja" liefert, falls x Î A gilt, und die Antwort "nein" sonst. Die Maschine hält immer. Sie berechnet die charakteristische Funktion.

Wenn eine Menge A Í IN rekursiv-aufzählbar ist, gibt es lediglich eine Registermaschine, die für x Î IN die Antwort "ja" liefert, wenn x Î A gilt, und im Fall x Ï A keine Antwort liefert. Hier spiegelt sich wieder, dass die rekursiv-aufzählbaren Mengen genau die Definitionsbereiche der partiell berechenbaren Funktionen sind.
Beweis: Sei A rekursiv. Dann gibt es eine Maschine, die die charakteristische Funktion berechnet (s. o.). Diese Maschine muss nun so abgewandelt werden, dass sie bei dem Ergebnis "nein" (x Ï A) nicht anhält, sondern in einer Endlosschleife verweilt. Die Maschine berechnet dann eine partiell berechenbare Funktion f mit A = Def(f). Somit ist A auch rekursiv-aufzählbar.

Wenn eine Menge rekursiv-aufzählbar ist und ihr Komplement ist es auch:
Wie zeigt man, dass diese Menge auch rekursiv ist?
Hier konnte ich mir aussuchen, ob ich es auf der Ebene der Maschinen oder auf der Ebene der Funktionen erkläre.
Ich habe mich für die Funktionsebene entschieden: Der Beweis beruht auf dem Satz, dass eine Menge A Í IN rekursiv-aufzählbar ist, gdw. A = Æ oder A = Bild(g) für ein g Î R⁽¹⁾. Da also die Mengen A und IN \ A rekursiv-aufzählbar sind, gibt es Funktionen f, g Î R⁽¹⁾ mit A = Bild(f) und IN \ A = Bild(g). Somit muss eine Zahl y Î IN in einer der beiden Listen (f(0), f(1), ...) und (g(0), g(1), ...) vorkommen. Man konstruiert nun eine Funktion, die die beiden Listen parallel nach dieser Zahl durchsucht. Wird die Zahl in der Liste Bild(f) = A gefunden, gibt die Funktion eine 1 aus, ansonsten (wenn also die Zahl in Liste Bild(g)) eine 0. Die so konstruierte Funktion ist berechenbar. Offenbar handelt es sich um die charakteristische Funktion der Menge A. Daraus folgt: A ist rekursiv.
Prof. Weihrauch: "Sie hätten auch zwei Maschinen parallel laufen lassen können." (Hm, diese Beweisvariante wäre vielleicht einfacher/kürzer gewesen. Man lässt die Maschinen laufen, solange bis eine der beiden hält. Das entspricht dem parallelen Durchsuchen der Listen. Im Kurstext wird der Beweis auf Funktionsebene geführt. Deshalb war mir das zunächst vertrauter. Wenn ich es noch mal zu beantworten hätte, würde ich es auf Maschinenebene erklären.)

Welche Rolle spielen die rekursiv-aufzählbaren Mengen in der Logik?
Die Mathematik ist axiomatisch aufgebaut. Jedes in der Mathematik gebräuchliche Beweissystem (Axiomensystem) ist eine rekursive Menge. Die Mengen, der daraus ableitbaren (beweisbaren) wahren Sätze sind rekursiv-aufzählbar. Aus dem Namen einer solchen Menge kann ein weiterer wahrer Ausdruck hergeleitet werden. Die so erzeugten Ausdrücke sind nicht aus den Axiomen herleitbar! Daraus ergibt sich der erste Gödelsche Unvollständigkeitssatz, dass jedes widerspruchsfreie rekursive Axiomensystem unvollständig ist.

Im Kurs wurde die Programmiersprache j eingeführt. Was ist denn Kj?
Ich habe die Menge Kj = {i Î IN | j_i(i) existiert} aufgeschrieben und gesagt, dass sie rekursiv-aufzählbar, aber nicht rekursiv ist.

Der Beweis, dass Kj rekursiv-aufzählbar ist, ist ja einfach: Man macht es mit Hilfe der universellen Funktion. Aber wie zeigt man, dass Kj nicht rekursiv ist?
Es ist zu zeigen, dass IN \ Kj nicht rekursiv-aufzählbar ist. Man zeigt es durch Diagonalisierung über die Folge aller rekursiv-aufzählbaren Teilmengen von IN - also über (Def(j₀), Def(j₁), ...).
Hierzu habe ich die folgende Äquivalenzbeziehung aufgeschrieben:     i Î IN \ Kj Û i Ï Kj Û i Ï Def(j_i)
Daraus folgt, dass die Mengen IN \ Kj und Def (j_i) ungleich sind für alle i Î IN. Die Menge IN \ Kj stimmt also mit keiner rekursiv-aufzählbaren Menge überein und ist daher nicht rekursiv-aufzählbar. Weil das Komplement von Kj nicht rekursiv-aufzählbar ist, ist Kj nicht rekursiv.

Gut, dann kommen wir mal zur Komplexitätstheorie ...
Wir hatten den Zeitbedarf t_M(x) und den Bandbedarf s_M(x). Hängen die irgendwie zusammen?
Ich habe erklärt, was man unter Time-Space-Tradeoff versteht, und die Abschätzungsformeln aufgeschrieben. Außerdem sollte ich begründen, wie es zu den Abschätzungen kommt:

Für alle x Î Def ( f_M ) ist s_M(x) £ t_M(x) + k.
k ist der Bandbedarf der Anfangskonfiguration (zu Beginn ist auf jedem der k Arbeitsbänder genau ein Feld belegt - nämlich das Blank unter dem Kopf). t_M(x) ergibt sich daraus, dass man pro Rechenschritt (durch Anfügen eines Blanks) höchstens ein neues Feld hinzugewinnen kann.

Es gibt ein c Î IN, so dass t_M(x) £ (lg(x) + 1) × c^sM(x) für alle x Î Def( f_M ).
Die zweite Abschätzung hat etwas mit der Anzahl der möglichen Konfigurationen zu tun: Die Berechnung liefert bei Eingabe von x eine Folge von Konfigurationen. Bei einer haltenden Berechnung können zwei verschiedene Konfigurationen nicht äquivalent sein, sonst käme man nie aus der Berechnung heraus und hätte eine Endlosschleife! Die zweite Formel ergibt sich, wenn man die Anzahl der Äquivalenzklassen von Konfigurationen nach oben abschätzt.

Noch zur zweiten Formel: Warum ist die Abschätzung exponentiell?
Bei einem Band der Länge s und einem Alphabet mit g Zeichen (also g := card(G)) gibt es g^s Möglichkeiten, dieses Band zu beschreiben. Mehr wollte Prof. Weihrauch nicht hören und meinte: "Das reicht schon. Das ist die Stelle im Beweis, an der das Exponentielle reinkommt".

Was sind P und NP?
P ist die Menge aller in polynomieller  Zeitkomplexität deterministisch entscheidbaren Sprachen.
NP ist die Menge aller in polynomieller Zeitkomplexität nichtdeterministisch beweisbaren Sprachen.
Weil jeder deterministische Algorithmus ein Sonderfall eines nichtdeterministischen (mit nur einer Möglichkeit) ist, gilt: P Í IN. Aber ob P = NP gilt, ist bisher noch nicht geklärt und ist eines der zentralen Probleme der theoretischen Informatik.

Nennen Sie mir ein Maschinenmodell, was wir im Zusammenhang mit den nichtdeterministischen Komplexitätsklassen kennen gelernt haben!
Kontroll-Turingmaschine (KTM).

Wann wird denn ein Wort von einer Kontroll-Turingmaschine erkannt?
Ein Wort x wird von der KTM erkannt, genau dann wenn es mindestens ein Hilfseingabewort y Î {0, 1}^* gibt, so dass die Maschine bei Eingabe von (x, y) zu einer positiven Entscheidung gelangt (wenn also y ein Beweis für die Eigenschaft "x Î L" ist). Das Hilfseingabewort steht auf Band 0.
Auch hier reichte die verbale Umschreibung. Die Menge L_M = {x Î S^* | $ y Î {0, 1}^*.t_M(x, y) = 1} musste ich nicht aufschreiben.

Nehmen wir mal 3SAT. Was steht hier bei der KTM auf Band 0?
Die Belegung (Werte) der Variablen. Die KTM prüft dann in polynomieller Zeit, ob die Formel bei dieser Belegung erfüllbar ist oder nicht.

Hier war die Prüfung zu Ende. Formale Sprachen wurden nicht geprüft.

Fazit: Ich kann mich den bisherigen Prüfungsprotokollen nur anschließen. Prof. Weihrauch ist als Prüfer uneingeschränkt zu empfehlen. Die Prüfungsatmosphäre war sehr freundlich. Es war eher ein Gespräch als ein Frage-Antwort-Spiel. Prof. Weihrauch gestaltet die Prüfung wie eine Kurszusammenfassung. Die Fragen ergeben sich immer aus dem Kontext. Wenn man die Zusammenhänge verstanden hat, kann eigentlich nichts schief gehen. Es ist auch nicht schlimm, wenn mal eine falsche Antwort herausrutscht (mir passiert bei 3SAT). Wenn man den Fehler noch selbst korrigieren kann, hat es keine negativen Konsequenzen.

Vorbereitung: Schon zur Vorbereitung auf die Klausur habe ich die Betreuungsangebote in den Studienzentren wahrgenommen. Wer irgendwie die Möglichkeit hat, an solchen Veranstaltungen teilzunehmen, sollte dies zu tun. Dabei lernt man vor allem, über den Stoff zu reden.
Viel gebracht haben mir auch die vom Lehrgebiet Theoretische Informatik I veranstalteten Studientage. Diese sind auch als Vorbereitung auf die mündliche Prüfung sehr gut geeignet. Dort wurde zu jedem Themenschwerpunkt ein kurzer Vortrag gehalten. Anschließend wurden in Kleingruppen die zugehörigen Aufgaben besprochen.
Die Schwerpunkte der mündlichen Prüfung kann man gut anhand der schon vorhandenen Gedächtnisprotokolle erkennen. Grundlage für meine Vorbereitung war zunächst das Lernskript von Thomas Schwarze. Das habe ich dann anhand der jüngeren Protokolle noch etwas ergänzt. Anschließend habe ich den Kurstext mit Blick auf die am Ende einer jeden KE genannten Lernziele durchgearbeitet und mir das, was noch in meinen Aufzeichnungen fehlte, herausgeschrieben.

Wer die Klausur bestanden hat (und das haben ja alle, die zur mündlichen Prüfung fahren :-)), der muss sich hier wirklich keine Sorgen machen.

Zu 1653/1654 habe ich folgende Betreuungsangebote wahrgenommen:

Viel Glück bei Euren Prüfungen !!!