Musical Notation <musicdenotat...@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 <p...@vanoostrum.org> WWW: http://pietvanoostrum.com/ PGP key: [8DAE142BE17999C4] -- http://mail.python.org/mailman/listinfo/python-list