Re: Lambda function Turing completeness

References	<5CB71036-C359-4211-8B3B-62B17AACF88E@gmail.com>
From	Ian Kelly <ian.g.kelly@gmail.com>
Date	2013-07-31 11:07 -0600
Subject	Re: Lambda function Turing completeness
Newsgroups	comp.lang.python
Message-ID	<mailman.40.1375290509.1251.python-list@python.org> (permalink)

Show all headers | View raw

On Wed, Jul 31, 2013 at 12:53 AM, Musical Notation
<musicdenotation@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)

Back to comp.lang.python | Previous | Next | Find similar | Unroll thread

Thread

Re: Lambda function Turing completeness Ian Kelly <ian.g.kelly@gmail.com> - 2013-07-31 11:07 -0600

csiph-web