Lambda-Kalkül als universelles Modell

• Wahrheitswerte:

  $\sf True$ = λxy.x,$\sf False$ = λxy.y

  (damit läßt sich if-then-else leicht aufschreiben)

• natürliche Zahlen:

  0 = λx.x;(n + 1) = 〈$\sf False$ , n〉

  (damit kann man leicht x > 0 testen)

• Rekursion mit Fixpunkt-Kombinator

Satz: Menge der berechenbaren Funktionen (mit Turingmaschine, while-Programm) = Menge der Lambda-berechenbaren Funktionen (mit dieser Kodierung)