Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.lang.python > #51674 > unrolled thread

Re: Lambda function Turing completeness

Back to article view | Back to comp.lang.python

This discussion starts older than the indexed window; earlier articles aren't shown. The article labeled Started by below is the oldest one visible, not the original post.

Contents

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

#51674 — Re: Lambda function Turing completeness

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)

[toc] | [standalone]

Back to top | Article view | comp.lang.python

csiph-web