Kurzbeschreibung Berechenbarkeit

Berechenbarkeit
Kurzbeschreibung

Gegenstand der Vorlesung sind Präzisierungen des Begriffs der "berechenbaren'' Funktionen, der Nachweis der Äquivalenz verschiedener Ansätze hierzu und die Untersuchung der dadurch festgelegten Klasse der (partiell) rekursiven Funktionen.

Inhalte sind insbesondere:

abstrakte Maschinen allgemein, speziell Turingmaschinen und Registermaschinen
LOOP- und WHILE-Berechenbarkeit
Definitionsprinzipien: primitive Rekursion, beschränkte Minimierung, unbeschränkter Suchoperator
primitiv rekursive, rekursive, partiell rekursive Funktionen; rekursive und rekursiv aufzählbare Mengen
Kleenes Normalformtheorem, universelle Funktionen, Rekursionstheorem, Satz von Rice
kurze Einführung in die Komplexitätstheorie