Is it true that "A function is primitive recursive iff the order needed to prove the induction is at most $\omega$ ."

46 Views Asked by At

At the end of this question a user states

A function is recursive primitive iff the order needed to prove the induction is at most $\omega$.

Intuitively this makes sense, but is it true? Ackerman is not primitive recursive, which implies the order needed is not at most $\omega$. But Ackerman always terminates in a finite amount of time. Am I not understanding how Ackerman grows faster than any primitive recursive function? Or is the quoted statement not entirely correct?