Prüfer: Hr. Prof. Dr. Weihrauch

Datum: 26.04.99

Note: 1,0

• Wann ist eine Zahlenfunktion berechenbar
• Ist x² berechenbar
• Zusammenhang zwischen eine Funktion "heißt" und eine Funktion "ist" berechenbar -> Churchsche These
• Datenmenge einer Bandmaschine mit Erklärung für (u,a,v)
• Befehlssatz einer Bandmaschine
• Kommt eine Bandmaschine ohne Hilfssymbole aus -> Hilfssymbollemma
• Zusammenhang zwischen Zahlen- und Wortberechenbarkeit
• Anforderungen an Modellsprache phi -> Anforderungen (U) und (S) erläutert, Hinweis auf utm- und smn-Theorem als formale Anforderung
• Definition von phi
• Berechenbarkeit auf Q
• Definition von (nrat, nrat) – berechenbar
• Ausweitung auf Berechenbarkeitsbegriff in R
• Definition Cauchy- Darstellung
• Typ-2-Maschine, Arbeitsweise erläutern
• Beispiele für Funktionen, die auf R berechenbar sind -> x², Wurzel(x), x+y
• Zwei Definitionen zu rekursiven Mengen
• Drei Definitionen zu rekursiv aufzählbaren Mengen
• Zusammenhang zwischen den Mengen
• Menge, die r.a. aber nicht rekursiv ist -> K phi
• Beweis, daß K phi r.a.
• Beweis, daß N\K phi nicht r.a.
• Ist die Menge der geraden Zahlen rekursiv
• Ist L={w aus {0,1}* mit 010 als Teilwort} regulär -> Angabe eines endlichen Automaten
• Ist L={wwR} kontextfrei -> Erkennung durch nichtdeterministen Kellerautomat

Komplexitätstheorie wurde nicht geprüft.