Equational derivation vs. computation (Q1338198): Difference between revisions

Subrecursive hierarchy classifications are used to compare the complexities of recursive functions according to (i) their derivations in a version of Kleene's equation calculus, and (ii) their computations by term-rewriting. In each case ordinal bounds are assigned, and it turns out that the respective complexity measures are given by (i) a version of the Fast Growing Hierarchy, and (ii) the Slow Growing Hierarchy. Known comparisons between the two hierarchies then provide ordinal tradeoffs between (i) derivation and (ii) computation. Characterizations of some well-known subrecursive classes are also read off.