Some subrecursive versions of Grzegorczyk's Uniformity Theorem

A theorem published by A. Grzegorczyk in 1955 states a certain kind of effective uniform continuity of computable functionals whose values are natural numbers and whose arguments range over the total functions in the set of the natural numbers and over the natural numbers. Namely, for any such functional a computable functional with one function‐argument and the same number‐arguments exists such that the values of the first of the functionals at functions dominated by a given one are completely determined by their restrictions to numbers not exceeding the corresponding values of the second functional at the given function. We prove versions of this theorem for the class of the primitive recursive functionals and for the class of the elementary recursive ones. Analogous results can be proved for many other subrecursive classes of functionals. (© 2004 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)