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

Groups > comp.lang.python > #45243

Re: Python for philosophers

Show all headers | View raw

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

Back to comp.lang.python | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll thread

Thread

Re: Python for philosophers Citizen Kant <citizenkant@gmail.com> - 2013-05-12 16:17 +0200
  Re: Python for philosophers Steven D'Aprano <steve+comp.lang.python@pearwood.info> - 2013-05-12 14:30 +0000
    Re: Python for philosophers alex23 <wuwei23@gmail.com> - 2013-05-12 21:19 -0700
  Re: Python for philosophers rusi <rustompmody@gmail.com> - 2013-05-12 09:00 -0700
  Re: Python for philosophers Gregory Ewing <greg.ewing@canterbury.ac.nz> - 2013-05-13 12:34 +1200
    Re: Python for philosophers Steven D'Aprano <steve+comp.lang.python@pearwood.info> - 2013-05-13 02:41 +0000
      Re: Python for philosophers rusi <rustompmody@gmail.com> - 2013-05-13 07:53 -0700
        Re: Python for philosophers Chris Angelico <rosuav@gmail.com> - 2013-05-14 02:24 +1000
          Re: Python for philosophers rusi <rustompmody@gmail.com> - 2013-05-13 11:14 -0700
            Re: Python for philosophers Chris Angelico <rosuav@gmail.com> - 2013-05-14 04:22 +1000
          Re: Python for philosophers 88888 Dihedral <dihedral88888@googlemail.com> - 2013-05-18 16:56 -0700
            Re: Python for philosophers Chris Angelico <rosuav@gmail.com> - 2013-05-19 10:04 +1000
              Re: Python for philosophers 88888 Dihedral <dihedral88888@googlemail.com> - 2013-05-18 19:30 -0700
                Re: Python for philosophers Michael Torrie <torriem@gmail.com> - 2013-05-18 22:46 -0600
    Re: Python for philosophers Schneider <js@globe.de> - 2013-05-16 16:13 +0200
  Re: Python for philosophers Steven D'Aprano <steve+comp.lang.python@pearwood.info> - 2013-05-13 03:25 +0000
    Re: Python for philosophers Grant Edwards <invalid@invalid.invalid> - 2013-05-13 14:33 +0000
  Re: Python for philosophers Steven D'Aprano <steve+comp.lang.python@pearwood.info> - 2013-05-13 07:13 +0000
    Re: Python for philosophers alex23 <wuwei23@gmail.com> - 2013-05-13 02:05 -0700
    Re: Python for philosophers Neil Cerutti <neilc@norwich.edu> - 2013-05-13 13:52 +0000

csiph-web