Ackermann function

The Ack­er­mann func­tion works as fol­lows:

One may have no­ticed that ad­di­tion, mul­ti­pli­ca­tion, and ex­po­nen­ti­a­tion seem to in­crease in “power”, that is, when pit­ted against each other, it is eas­ier to pro­duce enor­mous num­bers with ex­po­nen­ti­a­tion than with mul­ti­pli­ca­tion, and so on.

The Ack­er­mann func­tion pro­duces a hi­er­ar­chy of such growth op­er­a­tions, and as­cends one step higher in the hi­er­ar­chy each time.

Ad­di­tion is the first op­er­a­tor in the hi­er­ar­chy (though if we wanted, we could define ad­di­tion as re­peated suc­ces­sion and de­clare ad­di­tion the sec­ond op­er­a­tor in the hi­er­ar­chy). The next op­er­a­tor in the hi­er­ar­chy is pro­duced by iter­at­ing the pre­vi­ous el­e­ment in the hi­er­ar­chy. For in­stance, the next few op­er­a­tors in the hi­er­ar­chy are mul­ti­pli­ca­tion, ex­po­nen­ti­a­tion, and tetra­tion:

Mul­ti­pli­ca­tion is iter­ated ad­di­tion: \(A \cdot B = \underbrace{A + A + \ldots A}_{B \text{ copies of } A}\)

Ex­po­nen­ti­a­tion is iter­ated mul­ti­pli­ca­tion: \(A^B = \underbrace{A \times A \times \ldots A}_{B \text{ copies of } A}\).

(\(A ^ B\) is writ­ten \(A \uparrow B\) in knuth up ar­row no­ta­tion.)

Te­tra­tion is iter­ated ex­po­nen­ti­a­tion.\(A \uparrow\uparrow B = \underbrace{A^{A^{\ldots^A}}}_{B \text{ copies of } A}\) times.

\(\uparrow^n\) just means \(n\) up ar­rows, so we can also write tetra­tion as: \(A \uparrow^2 B = \underbrace{A \uparrow^1 (A \uparrow^1 (\ldots A))}_{B \text{ copies of } A}\)

Now the pat­tern can be no­ticed and gen­er­al­ized, fol­low­ing the rule: \(A \uparrow^n B = \underbrace{A \uparrow^{n-1} (A \uparrow^{n-1} (\ldots A))}_{B \text{ copies of } A}\)

And now we can define the Ack­er­mann func­tion as \(A(n) = n \uparrow^n n\).

This defi­ni­tion is rel­a­tively small, but the func­tions grow at in­cred­ible rates. Wait But Why has a good in­tu­itive de­scrip­tion of how in­cred­ibly fast tetra­tion, pen­ta­tion, and hex­a­tion grow, but by the time we get to \(A(6)\), the Ack­er­mann func­tion already grows far more quickly than that. \(A(1)=1\), \(A(2)=4\), and \(A(3)\) can­not be writ­ten in the uni­verse, as it has enor­mously more digits than our uni­verse has sub­atomic par­ti­cles.

In­ter­est­ingly enough, the Ack­er­mann func­tion grows faster than all prim­i­tive re­cur­sive func­tions. This is re­lated to a rather deep con­nec­tion be­tween the con­sis­tency strength of a math­e­mat­i­cal the­ory (which sorts of re­sults they are ca­pa­ble of prov­ing) and the slow­est-grow­ing func­tion for which the the­ory can­not prove “this func­tion is defined on all in­te­gers.”