Lambda function Turing completeness

[Ian Kelly]

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)