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)

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)



2009-11-20