Rechnen mit simulierten Zahlen

Church-Kodierung der natürlichen Zahlen (Alonzo Church, 1903-1995, http://www-history.mcs.st-andrews.ac.uk/Biographies/Church.html)

• Idee: [n] = $\lambda$fx.fⁿ(x)

• Null: [0] = $\lambda$fx.x(= K),
• Nachfolger: [n + 1] = $\lambda$fx.[n]f (fx), also succ = $\lambda$nfx.nf (fx)

• 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)