mtak Test Program

Highly recursive functions that majored primitive recursive functions have already been in-vented by Ackerman in the late 1920s. In 1970s Takeuchi came up with a highly recursive function that has astonishing simple closed form solution. The recursive function is:

                | Y            for X <= Y    
tarai(X,Y,Z) := |
                | tarai(tarai(x-1,y,z),tarai(y-1,z,x),tarai(z-1,x,y))

And its close form:

                | Y            for X <= Y    
                |
tarai(X,Y,Z) := | Z            for Y <= Z
                |
                | X

But McCarthy spoiled it all by a slight modification. Instead of returning Y in the first case of the recursive definition, in his version the value of Z is returned. This function has to become known as the tak function.

One test iteration will compute the tak function for the arguments (18, 12, 6).

Kommentare