Re: Lambda function Turing completeness
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
Re: Lambda function Turing completeness
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 p...@vanoostrum.org WWW: http://pietvanoostrum.com/ PGP key: [8DAE142BE17999C4] -- http://mail.python.org/mailman/listinfo/python-list
Re: Lambda function Turing completeness
On Wed, 31 Jul 2013 13:53:26 +0700, Musical Notation wrote: Is it possible to write a Turing-complete lambda function (which does not depend on named functions) in Python? lambda s: eval(s) -- Steven -- http://mail.python.org/mailman/listinfo/python-list
Re: Lambda function Turing completeness
On Wed, Jul 31, 2013 at 11:55 PM, Steven D'Aprano steve+comp.lang.pyt...@pearwood.info wrote: On Wed, 31 Jul 2013 13:53:26 +0700, Musical Notation wrote: Is it possible to write a Turing-complete lambda function (which does not depend on named functions) in Python? lambda s: eval(s) eval is a named function. -- http://mail.python.org/mailman/listinfo/python-list
Re: Lambda function Turing completeness
On Wed 31 Jul 2013 08:53:26 AM CEST, Musical Notation wrote: Is it possible to write a Turing-complete lambda function (which does not depend on named functions) in Python? what should a sinlge Turing-complete lambda function be? For me, a programming language can be Turing-complete or a function can be universal, e.g. like an interpreter for a programming language. bg, Johannes -- GLOBE Development GmbH Königsberger Strasse 260 48157 MünsterGLOBE Development GmbH Königsberger Strasse 260 48157 Münster 0251/5205 390 -- http://mail.python.org/mailman/listinfo/python-list
Re: Lambda function Turing completeness
On Wed, Jul 31, 2013 at 12:53 AM, Musical Notation musicdenotat...@gmail.com wrote: Is it possible to write a Turing-complete lambda function (which does not depend on named functions) in Python? Yes, lambda functions are Turing-complete. You can get anonymous recursion by defining the function to take a recursive function argument and then passing it to itself. For example, this will (inefficiently) give you the 13th Fibonacci number: (lambda f, n: f(f, n))(lambda f, n: n if n 2 else f(f, n-2) + f(f, n-1), 13) -- http://mail.python.org/mailman/listinfo/python-list
Re: Lambda function
On Wed, 2009-02-25 at 17:56 +0530, aditya saurabh wrote: I defined two functions - lets say fa = lambda x: 2*x fb = lambda x: 3*x Now I would like to use fa*fb in terms of x is there a way? Thanks in advance I'm not sure what use fa*fb in terms of x means. But if you mean fa(x) * fb(x) then it's just: fa(x) * fb(x) -a -- http://mail.python.org/mailman/listinfo/python-list
Re: Lambda function
En Wed, 25 Feb 2009 12:42:32 -0200, Albert Hopkins mar...@letterboxes.org escribió: On Wed, 2009-02-25 at 17:56 +0530, aditya saurabh wrote: I defined two functions - lets say fa = lambda x: 2*x fb = lambda x: 3*x Now I would like to use fa*fb in terms of x is there a way? Thanks in advance I'm not sure what use fa*fb in terms of x means. But if you mean fa(x) * fb(x) then it's just: fa(x) * fb(x) I think he wants function composition, fb(fa(x)): def compose(*funcs): def composed(x, funcs=funcs): for f in reversed(funcs): x = f(x) return x return composed def square(x): return x**2 def plus1(x): return x+1 # same as plus1 = lambda x: x+1 but I like the def syntax y = compose(square, plus1) # y=(x+1)**2 y(3) # - 16 (or is it fa(fb(x))?) -- Gabriel Genellina -- http://mail.python.org/mailman/listinfo/python-list
