5

Here is the function:

if (m == 0)
    return n + 1;
else if (n == 0)
    return A(m-1, 1);
else
    return A(m-1, A(m, n-1));

This seems like an interesting function, especially since its values grow quite rapidly (my computer crashes if I try to run A(4,2) or A(3,10)).

From the wikipedia page it seems like it was only invented to show that a total computable function does not have to be primitive recursive. Has anything practical come from this function, other than homework problems in a computer science class?

  • 1
    The inverse of Ackermann's Function is useful in computational complexity, eg in line arrangements. – lhf May 19 '13 at 03:00
  • 1
    @lhf That counts, too, if you would like to make up an answer. They would not have made the inverse without having made the original first. –  May 19 '13 at 03:17
  • Oddly enough, the answer is yes. But justification is not needed. – André Nicolas May 19 '13 at 03:33
  • See also http://stackoverflow.com/questions/1424303/uses-of-ackermann-function. – lhf May 19 '13 at 11:57
  • Someday you will be a teaching assistant (or teacher) in a course which deals with computable functions and PR functions, and you will look for a nice exercise for your students. Then you'll see how wonderful the Ackermann function is! It can be used to fill half a paper with questions leading to its constructions!! – Asaf Karagila May 19 '13 at 14:24

2 Answers2

1

The inverse of Ackermann's function is useful in computational complexity, for instance in line arrangements and other problems in computational geometry. It's appearance in the analysis of some concrete problems and algorithms is somewhat surprising. See

lhf
  • 216,483
1

We used the inverse of Ackermann's function in section 5 of our paper “Untangling planar graphs from a specified vertex position - Hard cases” devoted to straight line drawings of planar graphs.

Alex Ravsky
  • 90,434
  • Again, this is related to Davenport–Schinzel sequences, as in ref 2 of that paper. – lhf May 19 '13 at 14:27