most recent 30 from http://mathoverflow.net 2013-06-19T14:34:18Z http://mathoverflow.net/feeds/user/23947 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/97927/computational-complexity-of-primitive-recursive-functions AKS 2012-05-25T09:04:56Z 2012-08-03T05:25:33Z

<p>If we have a rewrite system for primitive recursive functions, which simplifies each term according to how the function was defined, then what is the computational complexity of this calculation? That is, what is the coplexity of the normalization procedure? I have heard a claim that for a closed term calculating the value of the function requires transfinte induction up to $\epsilon_0$. Is this true and where can I find a proof of this? </p> <p>For example in (Schwichtenberg &amp; Wainer 2012) there is a lemma which says that a primitive recursive function is computable in $F_{\alpha}$-bounded time, for some $\alpha&lt;\omega$, where the set of all $F_{\alpha}$ for $\alpha&lt;\epsilon_0$ is the Fast Growing Hierarchy. </p> <p>Is the measure of transfinite induction related to this way of bounding the complexity? </p>

http://mathoverflow.net/questions/97927/computational-complexity-of-primitive-recursive-functions/97965#97965 AKS 2012-05-28T07:29:47Z 2012-05-28T07:29:47Z

Thanks. I have confirmed that the claim that I head about TI up to $\epsilon_0$, was ment for G&#246;del's T (that is for functionals of higher types). My interest was in primitive recursive functions and their time-complexity. I'll have a look at the Grzegorczyk hierarchy.