Rekursionstheorie

Rekursionstheorie, mathematische Theorie der Berechenbarkeit; in der Rekursionstheorie werden u. a. die Begriffe Algorithmus und rekursive Funktion z. B. mithilfe sogenannter idealer Rechenmaschinen (z. B. Registermaschine, Turing-Maschine) präzisiert und untersucht.