On the structure of subrecursive degrees

摘要

Subrecursive degrees are partitions of computable (recursive) functions generated by strong reducibility orderings. Such reducibilities can be naturally characterized in terms of closure operations. Closure operations corresponding to standard reducibilities such as “primitive recursive,” etc., are computation time closed. It is shown that if the closure operation defining a strong reducibility satisfies certain axioms, then the partial ordering of the subrecursive degrees contains dense chains.