Lambda-Berechenbarkeit

Satz: (Church, Turing)

Menge der Turing-berechenbaren Funktionen

(Zahlen als Wörter auf Band)

=

Menge der while-berechenbaren Funktionen

(Zahlen als Registerinhalte)

=

Menge der Lambda-berechenbaren Funktionen

(Zahlen als Lambda-Ausdrücke)