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)

Johannes Waldmann 2007-01-30