Lambda function Turing completeness

[Piet van Oostrum]

Musical Notation <musicdenotation at gmail.com> writes:

> Is it possible to write a Turing-complete lambda function (which does
> not depend on named functions) in Python?

The wording of this question is questionable. Turing completeness is not
an attribute of a function, but of a system (for example a programming
language or a machine). It means that for every Turing machine you can
write a program in that language or program the machine in such a way
that it emulates that Turing machine.

So you could ask if the subset of the Python programs consisting only of
a lambda expression is Turing complete. Or alternatively if for every
Turing machine you can write a lambda expression that emulates that
Turing machine.

It has been proven that the λ calculus is equivalent to Turing machines,
so if the lambda calculus can be emulated with Python's lambda
expressions the answer is yes. In the lambda calculus you can define
lambda expressions and apply functions to parameters. The parameters may
be functions (in fact in the pure λ calculus there is nothing else), so
functions must be first class citizens. Fortunately in Python this is
the case. So we suspect it can be done.

An important result in the λ calculus is that every expression can be
expressed in three functions S, K and I with only function application.
So we are going to try to do these in Python and see if it works.

The definitions in the λ calculus are:

S = λ x y z. (x z) (y z)
K = λ x y. x
I = λ x. x

The dot is used where Python uses :, function application is written as
juxtaposition: f x and λ x y is an abbreviation of λ x. λ y

So we are going to translate these in python. We have to explicitely
write the lambda's (each one with a single parameter) and add
parentheses around the function arguments if not already there.

>>> S = lambda x: lambda y: lambda z: x(z) (y(z))
>>> K = lambda x: lambda y: x
>>> I = lambda x: x

Now there is a theorem that SKK == I (I is the identity), so we are
going to test that:

>>> S(K)(K)('test')
'test'

a few more tests:

>>> for x in range(100):
...     if S(K)(K)(x) != I(x):
...         print('Not equal for x = %s' % x)
... 

All seem to be equal.

Of course we still have used names for the functions, but this is not
essential. We can just replace each of S, K, and I with their
definition:

>>> print((lambda x: lambda y: lambda z: x(z) (y(z))) # S
...         (lambda x: lambda y: x)                   # (K)
...           (lambda x: lambda y: x)('test'))        # (K) ('test')
test

>>> for x in 'ABCDEFGHIJKLMNOPQRSTUVWXYZ':
...     if ((lambda x: lambda y: lambda z: x(z) (y(z)))
...         (lambda x: lambda y: x)
...         (lambda x: lambda y: x)(x)) != (lambda x: x)(x):
...       print('Not equal for x = %s' % x)
... 
Success!

Now the pure λ lambda calculus has to express inter=gers, booleans etc.
also as lambda expressions and this makes it really unwieldy. However,
you can add some standard functions or expressions for these and that
doesn't diminish the expressiveness of the calculus. So I suppose that
you want to allow the use of all standard Python functions and
expressions.

Modern Pythons have conditional expressions, so this helps. We don't
have to emulate booleans and conditions with weird lambda expressions.
In Python's lambda expressions you can not use statements, only
expressions, so without conditional expressiosn Python's booleans
wouldn't be very useful.

The remaining problem is how to use loops or recursion. I'll do that in
a separate posting.
-- 
Piet van Oostrum <piet at vanoostrum.org>
WWW: http://pietvanoostrum.com/
PGP key: [8DAE142BE17999C4]