Python use growing or shrinking

Francois Pinard pinard at
Wed Jan 22 02:48:53 CET 2003

[Grzegorz Adam Hankiewicz]

> Do you have a link to a Turing-Complete language? I have here some
> text to process of infinite lentgh... <wink>

Here is a far less demanding exercise.  Merely print ackerman(4, 4):

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))

A bit of inspection and pondering should convince you that this function
always terminate for any non-negative integer i and j.

The most aggressive arithmetic operation above, which might increase the
value of the result, is the mere addition of `1'.  Sounds easy enough?
After you publish the answer here, only then should you wander into
something fundamentally bigger, like Turing machines :-).

François Pinard

More information about the Python-list mailing list