Lambda function Turing completeness
Ian Kelly
ian.g.kelly at gmail.com
Wed Jul 31 19:07:45 CEST 2013
On Wed, Jul 31, 2013 at 12:53 AM, Musical Notation
<musicdenotation at 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)
More information about the Python-list
mailing list