This is also true of the better-known Ackermann function.
In 1926, David Hilbert conjectured that every computable function was primitive recursive.
This was refuted by Gabriel Sudan and Wilhelm Ackermann — both his students — using different functions that were published in quick succession: Sudan in 1927,[1] Ackermann in 1928.
[3] The last equation can be equivalently written as These equations can be used as rules of a term rewriting system (TRS).
leads to the rewrite rules At each reduction step the rightmost innermost occurrence of F is rewritten, by application of one of the rules (r1) - (r3).