Python Turing machine

[François Pinard]

[Greg Ewing]

> "Delaney, Timothy" wrote:

> > Yeah - the dependence on an infinitely-long tape can be a real bugger ...

> well, any terminating computation only uses a finite amount of tape,
> so you just need to be prepared to buy more tape as needed.  Of course,
> if the universe is closed, you could find yourself in a situation of
> having run out of matter to make new tape from.

This situation is easily met.  Many of you known the Ackerman function:

def ackerman(i, j):
    if i == 0:
        return j + 1
    if j == 0:
        return ackerman(i-1, 1)
    return ackerman(i-1, ackerman(i, j-1))

in which, as you can see, the most "aggressive" operation towwards
bloating the resulting value is adding 1 to `j'.  When I was a teenager,
a few friends and I had a lot of fun at computing it for various small
argument values, but were just unable to climb the arguments to 4 and 4.

A few years later, having to spend a full night waiting, and to kill time,
I revisited the `ackerman(4, 4)' problem, to find out that the estimated
universe is much to small and much too young for having ever computed this
very odd value[1].

If each elementary particle of the universe was a bit, we would not have
enough bits.  If we consider one addition per unit of time, and the fastest
computer clock we can think of, there would not have been enough cycles
since the big bang.  For this computer, I set the clock period to the time
it takes for light to traverse a proton (which, contrarily to many thinks,
is much smaller than an electron).

Strange that such big a number, which is undoubtedly both well defined
and computable theoretically, could be represented by so little Python!

----------
[1] This was a while ago, maybe I do not remember well, but I got that
`ackerman(4, 4)' is `2 ** (2 ** (2 ** (2 ** (2 ** (2 ** 2))))) - 3'.
Because of this, I may dare writing that we get an odd number! :-)

-- 
François Pinard   http://www.iro.umontreal.ca/~pinard