On May 13, 7:41 am, Steven D'Aprano <steve
+comp.lang.pyt...@pearwood.info> wrote:
> Python is not well-modelled as a Finite State Machine. Python is
> equivalent in computing power to a Turing Machine, while Finite State
> Machines are much weaker, so there are things that Python can do that a
> FSM cannot.
Consider the following.
Python is turing-equivalent; so is C and scheme.
I now write a recursive factorial function in all 3.
[To level the pitch all three are written tail-recursively]
------------Python------------------
def fact(n,acc=1):
return acc if not n else fact(n-1,n*acc)
------------C-------------------------
#include <stdio.h>
main(int argc, char **argv)
{
printf("fact %d is %d\n", atoi(argv[1]), fact(atoi(argv[1],1)));
}
int fact(int n, int acc)
{
return !n? acc : fact(n-1,acc*n);
}
---------------------------------
When I run these, the C happily keeps giving answers until a million
The python crashes around a thousand.
However examined closely we find that though the C is giving answers
its giving junk after around 12
fact 17 is -288522240
And 35 onwards its 0 (!!)
So finally we do it in scheme:
(define (fact n ac)
(if (zero? n) ac (fact (1- n) (* ac n))))
--------------------------------------------------------
This program neither crashes (because of tail recursion) nor gives
wrong answers
However around 90000 my entire machine becomes completely unusable
with top showing guile (scheme) taking all the memory and kswapd next
in line.
So whats the moral?
The Turing model is essentially infinite.
[A TM to compute factorial would never crash because it can never be
built]
The machines we use are finite.
As a first approx we may say that languages like C,Python,Scheme are
Turing-complete.
However in fact when we have to stuff these (conceptually beautiful)
infinite objects into messy finite objects such as Intel hardware,
some corners have to be cut.
And these 3 -- C, Python, Scheme -- CUT THE CORNERS DIFFERENTLY
So when these corners dont matter -- Turing-equivalence is fine
When they do, we must make do living in a more messy finite world
--
http://mail.python.org/mailman/listinfo/python-list
