<div class="gmail_quote">On Wed, Apr 14, 2010 at 4:52 PM, Nick Coghlan <span dir="ltr"><<a href="mailto:ncoghlan@gmail.com">ncoghlan@gmail.com</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin: 0pt 0pt 0pt 0.8ex; border-left: 1px solid rgb(204, 204, 204); padding-left: 1ex;">
The course most likely to bear fruit is actually for people to identify<br>
what tools they need in the functools module in order to make Python<br>
expressions Turing complete<br></blockquote><div><br>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:<br>
<br>lambda n: ((lambda f, *args: f(f, *args))<br>               ((lambda f, n: 1 if n <= 0 else n*f(f, n-1)),n))<br><br>Using a similar scheme, one could write a state machine, which is sufficient to simulate the canonical Turing machine.<br>
<br>Of course, anyone writing a real algorithm using recursive lambda expressions deserves what they get. ;-)<br></div></div><div style="margin: 2em 0pt;" name="sig_2341e11ee1">--<br>
Daniel Stutzbach, Ph.D.<br>
President, <a href="http://stutzbachenterprises.com">Stutzbach Enterprises, LLC</a>
</div><br>