|
|
In article <1159992420.347384.266530@xxxxxxxxxxxxxxxxxxxxxxxxxxxx>,
Charlie-Boo <shymathguy@xxxxxxxxx> wrote:
>BTW I once wrote a program to generate lambda calculus expression and
>evaluate them for the first few natural numbers. I found identity,
>successor, addition, exponentiation, etc. But then I noticed that all
>of the functions were monotonic! At some point I read that they
>(Church?) hadn't been able to create subtraction, I believe it was.
>And years later someone claimed to have but using some kind of a trick.
> So, is lambda calculus really Turing complete?
One might argue that you can only represent the positive integers
in the lambda calculus using some kind of trick. Yes, the negative
integers can be represented and you can do subtraction and all sorts
of nice things in the lambda calculus (which is Turing complete).
I don't know of a "canonical" example, but
http://okmij.org/ftp/Computation/lambda-calc.html should provide
what you want.
Alan
--
Defendit numerus
|
|