Premium
Some subrecursive versions of Grzegorczyk's Uniformity Theorem
Author(s) -
Skordev Dimiter
Publication year - 2004
Publication title -
mathematical logic quarterly
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.473
H-Index - 28
eISSN - 1521-3870
pISSN - 0942-5616
DOI - 10.1002/malq.200310117
Subject(s) - mathematics , primitive recursive function , natural number , computable function , class (philosophy) , function (biology) , range (aeronautics) , argument (complex analysis) , discrete mathematics , pure mathematics , set (abstract data type) , computer science , biochemistry , chemistry , materials science , evolutionary biology , artificial intelligence , composite material , biology , programming language
Abstract 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)