Home Original page

[Python-ideas] @return?

Daniel Stutzbach daniel at stutzbachenterprises.com
Thu Apr 15 00:47:51 CEST 2010 
On Wed, Apr 14, 2010 at 4:52 PM, Nick Coghlan <ncoghlan at gmail.com> wrote:

> The course most likely to bear fruit is actually for people to identify
> what tools they need in the functools module in order to make Python
> expressions Turing complete
>

Unless I'm mistaken, Python's lambda expressions are already Turing
complete.  Below is a lambda expression for calculating the factorial of a
number, demonstrating that lambda expressions can use recursion:

lambda n: ((lambda f, *args: f(f, *args))
               ((lambda f, n: 1 if n <= 0 else n*f(f, n-1)),n))

Using a similar scheme, one could write a state machine, which is sufficient
to simulate the canonical Turing machine.

Of course, anyone writing a real algorithm using recursive lambda
expressions deserves what they get. ;-)
--
Daniel Stutzbach, Ph.D.
President, Stutzbach Enterprises, LLC <http://stutzbachenterprises.com>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.python.org/pipermail/python-ideas/attachments/20100414/8258d966/attachment.html>
More information about the Python-ideas mailing list