\begin{slide}{Rechnen mit simulierten Zahlen}

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

\begin{itemize}
\item
  Idee: $[n] = \lambda f x. f^n(x)$

\item
  Null:   $[0] = \lambda f x.x (= K)$, 
\item
  Nachfolger:
  $[n+1]=\lambda f x. [n] f (f x)$,
\renewcommand{\succ}{\operatorname{succ}}
  also $\succ = \lambda n f x. n f(f x)$

\item
  Dafür sind Nachfolger, Vorgänger, Null-Test definierbar.
\end{itemize}

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)

\end{slide}
%%% Local Variables: 
%%% mode: latex
%%% TeX-master: "~/edu/ws06/sym/folien/sym"
%%% End: 
