On Fri, Aug 3, 2012 at 2:12 AM, Adam P. Goucher <apgoucher@gmx.com> wrote:
The lambda calculus is a far more beautiful theory of computation than Turing Machines.
That's a very subjective statement. I don't particularly like the fact that lambda calculus involves giving variables arbitrary names. I much prefer combinatory logic to lambda calculus, which only has two primitive symbols {S = ^xyz.xz(yz), K = ^xy.x}. There are other two-combinator bases as well, where the complexity is distributed differently. Taking this to the extreme, where one of the combinators is the identity function, we have {P = ^vwxyz.wx(wzy), I = ^x.x}.
There's a simple one-combinator basis U = ^f.fSK I=UU K=U(U(UU)) S=U(U(U(UU))) -- Mike Stay - metaweta@gmail.com http://www.cs.auckland.ac.nz/~mike http://reperiendi.wordpress.com