Der Begriff der Berechenbarkeit spielt neben dem der Komplexität in der klassischen theoretischen Informatik eine zentrale Rolle. Zunächst sollte man sich fragen, was das Adjektiv „berechenbar“ überhaupt bedeutet und worauf sich dieser Begriff bezieht. Intuitiv werden viele darunter wohl verstehen, dass etwas „sich errechnen lässt“ bzw. „vorhersehbar“ ist. Um jedoch etwas berechnen zu können benötigt man sicherlich ein Kochrezept, also einen Algorithmus bzw. eine Funktionsvorschrift. Schließlich müssen wir auch noch klären, was man alles berechnen kann, es wird sich nämlich zeigen, dass nicht alle Funktionen berechnenbar sind.

Sowohl Turing- als auch Registermaschinen sind Modelle von Maschinen. Sie nähern sich der Frage nach der Berechenbarkeit von der Seite der berechenbaren Automaten. Die jeweiligen Programme, welche auf diesen Maschinen laufen, müssen spezielle für das jeweilige Modell und die jeweilige Problemstellung zugeschnitten sein.

Einen hiervon differeten (aber äquivalenten) Zugang zur Frage der Berechenbarkeit besiert auf speziellen Funktionenklassen und darauf abgeschlossenen Operationen (Verknüpfungen). Mit den so genannte rekursiven Funktionen werden wir Lösungen von Problemen beschreiben und nicht, wie es bei den Maschinenmodellen üblich ist, die einzelnen Schritte des Rechenweges. Das Modell der rekursiven Funktionen versucht also nicht eine Maschine bzw. einen Automaten nachzubilden, sondern packt das Problem der Berechnbarkeit sozusagen bei der Wurzel, d.h. es nähert sich der Frage nach der Berechenbarkeit von Seite der Algorithmen.

Im Einzelnen werden behandelt:

• Definition "intuitiv berechenbar"; Heranführung an den Begriff "Berechenbarkeit"; Grundlegende Definitionen
• Nicht berechenbare Funktionen und deren Existenz; Beispiele und Beweis; Kardinalitätsargument;
• Primitiv rekursive Funktionen; Induktionsprinzip; Basis-Funktionen; Grund-Funktionen; Konstante Funktionen; Nachfolgerfunktion (suc); Projektion auf den i-ten Eintrag; Substitution, Komposition, primitive Rekursion; primitiv rekursive Funktionen abgeschlossen gegenüber den Operationen; Beweis; Algorithmen; berechenbar;
• Arithmetische Funktionen primitiv rekursiv dargestellt: Addition, Multiplikation, Potenzierung, modifizierte Subtraktion, Fakultät, Signum-Funktion, Maximum, Minimum, Identität; Abgeschlossen gegenüber Umordnung und Weglassen von Variablen; Fallunterscheidung;
• Primitiv rekursive Relationen: Prädikate, Und, Oder, Nicht, Kleinergleich, Größergleich, Gleichheit; Charakteristische Funktion
• Der unbeschränkte mue-Operator; echte Erweiterung der primitiv rekursiven Funktionen; alle berechenbaren Funktionen; Minimalisierung; beschränkte mue-Operator; Beispiele;
• Ackermannfunktion; wichtigsten Charakterisierungen; Eigenschaften; Beweise; streng monoton in beiden Argumenten; wächst stärker als jede primitiv rekursive Funktion.