Page "Ackermann function" Paragraph 17

It may not be immediately obvious that the evaluation of always terminates.

However, the recursion is bounded because in each recursive application either m decreases, or m remains the same and n decreases.

Each time that n reaches zero, m decreases, so m eventually reaches zero as well.

( Expressed more technically, in each case the pair ( m, n ) decreases in the lexicographic order on pairs, which is a well-ordering, just like the ordering of single non-negative integers ; this means one cannot go down in the ordering infinitely many times in succession.

) However, when m decreases there is no upper bound on how much n can increase — and it will often increase greatly.