Aufgaben:........ 2
KE 1.............. 2
Flußdiagramme......... 2
Registermaschinen.... 2
KE 2.............. 2
Verfeinerung................ 2
Simulation 2
Beweis
(Charakterisierung r.a.).................. 2
KE 3.............. 2
Band-Maschinen 2
KE 4.............. 2
primitiv-rek, m-rek 2
Diagonalisierung......... 3
KE 5.............. 3
utm-Theorem,
smn-Theorem.. 3
KE 6.............. 3
Rekursive und r.a.
Mengen... 3
KE 7.............. 3
Numerierungen........... 3
Berechenbarkeit auf
reellen Zahlen..... 3
HK 92 Aufg 1 (Induktionsbeweis für Schleife)
Minimum zweier Zahlen berechnen
Maximum zweier Zahlen berechnen
NK 92 Aufg 1 (Induktion bei Bandmaschine)
HK 93 Aufg 1 (Induktion für ein FD einer RM)
NK 92 Aufg 2 (Induktion bei RM, Multiplikation)
HK 94 Aufg 1 (Induktion)
HK 96 Aufg 2 (mit Induktion)
HK 93 Aufg 1c
HK 93 Aufg 2
NK 92 Aufg 5 (Dualnotation)
HK 94 Aufg 3 (Darstellung endlicher Mengen)
HK 96 Aufg 1 (ganze Zahlen durch Worte und Band-Maschine)
HK 92 Aufg 4 (Anzahl von c und d in einem Wort, ohne Beweis)
HK 92 Aufg 5 (mit Beweis)
HK 93 Aufg 4 (mittlerer Buchstabe eines Wortes, ohne Beweis)
HK 96 Aufg 4 (führende Nullen streichen mit Beweis)
HK 93 Aufg 3
NK 92 Aufg 4 (Minimum-Funktion prim-rek)
Fibonacci-Zahlen sind primitiv-rek
Fakultät ist primitiv-rek
NK 93 Aufg 3 (Fallunterscheidungen)
HK 94 Aufg 2 (Fallunterscheidung und Summenbildung)
HK 96 Aufg 3 (Exponentation, Summation und Logarithmus)
NK 92 Aufg 8 (Potenzmenge von IN nicht numerierbar)
Die Menge der reellen Zahlen ist nicht abzählbar
Mathematische Texte sind nicht verstehbar
Die Menge aller Folgen mit 0 und 1 ist nicht numerierbar
Es gibt keine totale berechenbare Funktion, die die Nummern aller totalen berechenbaren Funktionen (von R) aufzählt. Warum gilt dies nicht für P?
HK 92, 7a
HK 94, 8
NK 93, 5
NK 92, 7
HK 96, 6
HK 92, 8
HK 92, 9
HK 94, 5
NK 93, 6
NK 92, 9
HK 96, 7
HK 92, 6 (Numerierung von Q)
HK 94, 7
NK 92, 6
HK 96, 5 (Numerierungen von Z mit Reduzierbarkeitsfragen)
Beweis des Äquivalenzsatzes von Rogers
Beweis des Satzes von Rogers
Berechenbarkeit der Addition
Berechenbarkeit der Multiplikation
Berechenbarkeit des Logarithmus
Berechenbarkeit der Exponentiation