Challenge Your Computer

I was bugged, bugged with the little stupid box which challenges my faculties of thinking with its inorganic AI abilities. Then my little grey cells came to my aid and dug out the one of the most wonderful problems that men invented. I am here referring to Ackerman Function.>>

This is what wikipedia has to say about it in the abstract: In the theory of computation, the Ackermann function or Ackermann-Péter function is a simple example of a recursive function that is not primitively recursive. It takes two natural numbers as arguments and yields another natural number. Its value grows extremely quickly; even for small inputs, for example (4,3), the values of the Ackermann function become so large that they cannot be feasibly computed, and in fact their decimal expansions require more digits than there are particles in the entire visible universe.

This function was conceptualized by Wilhelm Ackerman (1896-1962).>>

Wilhelm Ackermann received his doctoral degree in 1925 with a thesis written under Hilbert. Its content was a consistency proof of arithmetic without induction. From 1927 until 1961 he taught as a teacher at the Gymnasien in Burgsteinfeld and in Luedenscheid. He was corresponding member of the Akademie der Wissenschaften in Göttingen, and was honorary professor at the UniversitŠt Münster. He worked on logic with Hilbert.

In 1928, Ackermann observed that A(x,y,z), the z-fold iterated exponentiation of x with y, is an example of a recursive function which is not primitive recursive. A(x,y,z) was simplified to a function P(x,y) of 2 variables by Rosza Peter whose initial condition was further simplified by Raphael Robinson. This last function is called Ackermann's function in today's textbooks. Also in 1928, Hilbert and Ackermann coauthored the logic book Grundzuege der Theoretischen Logik.

Among Ackermann's later work there are consistency proofs for set theory, full arithmetic , and type free logic. He also gave a new axiomatization of set theory in 1956, and wrote the book Solvable cases of the decision problem in 1954.

The first time I saw this function in 2002, I was excited, and i ran a recursive implementation on of it on a linux machine. I executed it with just the inputs 10,10. Poor guy never recovered from this load and had to be powered off and on to get it back to normalancy. This is a deceptively simple function.>>

a (m,n) = n+1 if m=0
= a (m-1, 1) if m0, n=0
= a (m-1, a(m, n-1)) if m0, n0

And today, I was in a mood to actually send my machine bonkers, and what a nice way to do that.