Lambda function Turing completeness

[Piet van Oostrum]

This is the second part of my posting on the Turing completeness of
Python's lambda expressions. This time I am going to define a recursive
function as a lambda expression (I use lambda when I am talking about
Python's lambda expressions, and λ for the theory – λ calculus.)

Now of course it is easy to define a recursive function if you can use
its function name inside the body. But the question of the OP was if you
can do it without named functions. The pure λ calculus only works with
unnamed λ expressions. Therefore we need a special operator to define
recursive functions. This is the so called Y combinator, or Y
operator[1].

The defining characteristic of Y is:

Y(f)  = f(Y(f)) for all functions f.
 
There are several possible definitions of this operator, but some of
them work only for programming languages with lazy evaluation or call by
name. For Python's call by valye the following one will work:

Y = λf.(λx.f (λv.((x x) v))) (λx.f (λv.((x x) v)))

Translated in Python:

>>> Y = lambda f: (lambda x: f (lambda v: ((x (x)) (v)))) \
...                 (lambda x: f (lambda v: ((x (x)) (v))))

We are going to define a lambda expression for the factorial function.
We need a helper function for this. The idea is to have the final
recursive function as a parameter of the helper function. See [1].

def fact_helper(f, n):
    if n == 0:
        return 1
    else:
        return n * f(n-1)

No we have to rewrite this to get a proper lambda expression. We split
the two parameters and give each of them a lambda, and we replace the if
statement with a conditional expression.

>>> fact_helper = lambda f: lambda n: (1 if n == 0 else n * f(n-1))

Now we apply the Y combinator to fact_helper to get the recursive fact
function and check it:

>>> fact = Y (fact_helper)
>>> fact(5)
120

Of course to get pure we have to get rid of the names of the functions.
So we replace each of Y, fact and fact_helper with their definition:

>>> (lambda f: (lambda x: f (lambda v: ((x (x)) (v)))) \
...        (lambda x: f (lambda v: ((x (x)) (v))))) \
...        (lambda f: lambda n: (1 if n == 0 else n * f(n-1))) (5)
120

Lo and behold! We have the right answer.

Now writing a universal Turing machine as a single Python lambda
expression is left as an exercise for the reader.

BTW. If you use Python 3 you can have print inside a lambda expression,
so this makes all this even nicer.
--------------
[1] http://en.wikipedia.org/wiki/Fixed-point_combinator#Y_combinator
-- 
Piet van Oostrum <piet at vanoostrum.org>
WWW: http://pietvanoostrum.com/
PGP key: [8DAE142BE17999C4]