On the structure of subrecursive degrees

✍ Scribed by Sanat K. Basu

• Publisher: Elsevier Science
• Year: 1970
• Tongue: English
• Weight: 549 KB
• Volume: 4
• Category: Article
• ISSN: 0022-0000
• DOI: 10.1016/s0022-0000(70)80042-3

✦ Synopsis

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.

PRELIMINARIES

Let X denote the nonnegative integers and ~,(~) be the class of partial-recursive (recursive) functions of n variables. We shall use the standard indexing of partial recursive functions, satisfying the universal function theorem and the s-m-n theorem [1]. Let ~i denote the partial function computed by the i-th Turing Machine in the standard indexing. @i will denote the step counting function corresponding to ~i 9 @i(x) will be interpreted as the number of steps used by the i-th T.M. in computing ~i(x) if ~i(x) converges. ~i(x) is undefined otherwise. If ~i is a recursive function, then so is ~i-Axiomatic characterization of the step counting functions is given by Blum

is elementary in x and y. Equivalently, ~i is honest if there is an elementary function v(x, y) such that ~i(x) < v(x, $i(x)) for almost all x.

A mapping F from functions of one variable to functions of one variable is called an operator. For any function f, the value of F(f) at x will be written as F(f, x). If 9 An earlier version of these results were presented at the ACM Symposium on Theory of Computing,