Rechnen mit simulierten Zahlen

• Wahrheitswerte T = $\lambda$xy.x, F = $\lambda$xy.y

  denn BMN$\to$M oder BMN$\to$N für B $\in$ {T, F}

• Zahlen:

  [0] = I,[n + 1] = $\lambda$x.xF[n]

• Dafür sind Nachfolger, Vorgänger, Null-Test definierbar.

mit Fixpunktsatz gibt es auch Rekursion (beliebige Schleifen), also ist jede Turing-berechenbare Funktion auch Lambda-berechenbar (und umgekehrt).

Übung: Addition, Multiplikation, Potenzieren

(tatsächlich ist das Modell älter als die Turing-Maschine)