Lambda-Berechenbarkeit

Satz: (Church, Turing)

Menge der Turing-berechenbaren Funktionen

(Zahlen als Wörter auf Band)

= mathend000#

Menge der while-berechenbaren Funktionen

(Zahlen als Registerinhalte)

= mathend000#

Menge der Lambda-berechenbaren Funktionen

(Zahlen als Lambda-Ausdrücke)