Schemat dowodu twierdzenia funkcja Ackermanna nie jest pierwotnie rekurencyjna: definiuje się rodzinę funkcji Ackermanna (każda z tych funkcji jest pierwotnie rekurencyjna). Z tego wynika, że każda funkcja pierwotnie rekurencyjna jest majoryzowana przez pewną funkcję Ackermanna. Następnie dowodzi się, że wszystkie jednoargumentowe funkcje Ackermanna będą z kolei majoryzowane przez funkcję Wynika z tego, że nie jest pierwotnie rekurencyjna.
Dowód przez indukcję:
Niech m = 0. Wtedy:
zgodnie z definicją dla funkcji posiadającej 0 jako pierwszy argument. z kolei jest zawsze większe od 0, ponieważ już w przypadku n = 0, n + 1 = 0 + 1 = 1.
(Hipoteza 1) Zakładając, że obowiązuje:
pokazujemy poprzez indukcję na argumencie n, że
W tym celu niech n = 0. Zgodnie z hipotezą 1 obowiązuje
i poprzez to
wedle definicji funkcji dla argumentu n = 0.
(Hipoteza 2) Zakładając, że obowiązuje:
pokazujemy, że
Ponieważ wedle hipotezy 2 zachodzi: musi obowiązywać:
a następnie zgodnie z hipotezą 1:
oraz wedle definicji funkcji dla argumentów różnych od 0:
Łącząc te trzy relacje otrzymujemy dowód twierdzenia: