Exercise idea: Ackermann(4,2)

Exercism
1

The answer is a power tower and requires a language to do bignums. Probably a difficulty >8.

2

You’ll need to do a good job of explaining it, as after googling I have no idea what it means :grin:

3

The Ackerman function is a very simple recursive function. It is of theoretical interest in mathematics, but only in ways that do not concern you. (I think.)

If you must know:

  • It is a computable function, which basically means that you (yes, you) can write a program that computes its output for any given input, but
  • It is not primitive recursive, which basically means that for-loops as a looping construct are not enough to be able to express it: you also need while-loops.
  • For some time in the past it was unknown whether any such functions – computable but not primitive recursive – exist. The Ackerman function, being an example of one, is proof that they do.

I need more information about your confusion to be able to explain more.

4

To calculate Ackermann 4,2 requires bignums. The task would be both to calculate 4,2 and implement a simple bignums library.

So, @MatthijsBlom , I’m not confused (well, no more than usual.)

5

I meant @iHiD, for