Lambda function Turing completeness

[Musical Notation]

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

 

[Steven D'Aprano]

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

lambda s: eval(s)

 

[Ian Kelly]

lambda s: eval(s)

eval is a named function.

 

[Piet van Oostrum]

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.

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

a few more tests:
.... 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:
.... (lambda x: lambda y: x) # (K)
.... (lambda x: lambda y: x)('test')) # (K) ('test')
test
.... 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]

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:
.... (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.

Now we apply the Y combinator to fact_helper to get the recursive fact
function and check it:
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 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.