Search

We show that the Turing degrees are not sufficient to measure the complexity of continuous functions on [0, 1]. Computability of continuous real functions is a standard notion from computable analysis. However, no satisfactory theory of degrees of continuous functions exists. We introduce the continuous degrees and prove that they are a proper extension of the Turing degrees and a proper substructure of the enumeration degrees. Call continuous degrees which are not Turing degrees non-total. Several fundamental results are proved: a continuous function with non-total degree has no least degree representation, settling a question asked by Pour-El and Lempp; every non-computable f ∈ [0,1] computes a non-computable subset of ℕ there is a non-total degree between Turing degrees a

Structure functions relate the level of operations of a system as a function of the level of the operation of its components. In this paper structure functions are studied which have an intuitive property, called L-superadditive (L-subadditive). Such functions describe whether a system is more series-like or more parallel-like. L-superadditive functions are also known under the names supermodular, quasi-monotone and superadditive and have been studied by many authors. Basic properties of both discrete and continuous (i.e., taking a continuum of values) L-superadditive structure functions are studied. For binary structure functions of binary values, El-Neweihi (1980) showed that L-superadditive structure functions must be series. This continues to hold for binary-valued structure functions even if the component values are continuous (see Proposition 3.1). In the case of non-binary-valued structure functions this is no longer the case. We consider structure functions taking discrete values and obtain results in various cases. A conjecture concerning the general case is made.

One of the basic differences between the primitive recursive functions on the natural numbers and the primitive recursive ordinal functions (PR) is the nearly complete absence of constant functions in PR. Since ω is closed under all of the functions in PR, if α is any infinite ordinal, then λξ·α is not in PR. It is easily seen, however, that if one adds to the initial functions of PR the constant function λξ·ω, then all of the ordinals up to ω#, the next largest PR-closed ordinal, have their constant functions in this class. Since, however, such collections of functions are always countable, it is also the case that if one adds to the initial functions of PR the function λξ. α for uncountable α, then there are ordinals β < α whose constant functions are not in this collection. Because of this, the following objects are of interest:Definition. For all α,(i)PR(α) is the collection of functions obtained by adding to the initial primitive recursive ordinal functions, the function λξ· α;(ii) PRsp(α), the primitive recursive spectrum of α, is the set {β < α ∣ λξβ ∈ PR(α);(iii) Λ (α)= μρ(ρ∉ PRsp(α)).

1.1 The system K* of basic logic, as presented in a previous paper, will be shown to be formalizable in an alternative way according to which the rule [E],is replaced by the rule [F],1.2. General recursive functions will be shown to be definable in K* in a way that retains functional notation, so that the equation,will be formalized in K* by the formula,where ‘f’, ‘p1’, … ‘pn’ respectively denote φ, x1, …, xn, and where ‘≐’ plays the role of numerical equality. Partial recursive functions may be handled in a similar way. The rule [E] is not required for dealing with primitive recursive functions by this method.1.3. An operator ‘G’ will be defined such that ‘[Ga ≐ p]’ is a theorem of K* if and only if ‘p’ denotes the Gödel number of ‘a’.1.4. In reformulating K* we assume ‘o0’, ‘o1,’ ‘o2’, …, have been so chosen that we can determine effectively whether or not a given U-expression is the mth member of the above series. The revised rules for K* are then as follows. (Double-arrow forms of these rules are derivable, except in the case of rule [V].)

Let ƒ be a real number. It is well known [7] that the set of rational numbers which are less than ƒ is a recursive set if and only if ƒ is representable as the limit of a recursive, recursively convergent sequence of rational numbers. In this paper we replace the condition that the set of rational numbers less than ƒ is recursive by the condition that this set is at various points in the Kleene hierarchy, and we replace the recursive, recursively convergent limit by a variety of other recursive limiting processes.

In a recent paper [4] on mean value theorems in recursive function theory we proved the theorem that(A) iff(n, x) is relatively differentiable with a relative derivative f1(n, x), for a ≤ x ≤ b, and if f(n, a) = f(n, b) = 0 relative to n,then there is a recursive function ck, a < ck < b, and a recursive R(k) such that f1(n, ck) = 0(k) for n ≥ R(k); and we showed further that the added condition(B) f(n, x) is either relatively variable or relatively constantsuffices to ensure that ck is uniformly contained in (a, b), i.e. that there exist α, β such thatA comparison with the conditions under which Rolle's theorem is established in classical analysis suggests that clause (A) itself might suffice to ensure that ck is uniformly contained in (a, b); for in the classical theory there is a single point c, a < c < b, for which lim f1(n, c) = 0, and therefore f1(n, c) = 0(k) for sufficiently great values of n, where of course c is independent of k.The object of the present note is to show that this is not in fact the case, and we shall construct a recursive function f(n, x) satisfying condition (A) in the interval (0, 1) and such that any sequence ck for which f1(n, ck) = 0(k) for large enough values of n is not uniformly contained in (0, 1).

Let be the set of recursive functions computable by machines using at most t(x) computation steps on argument x, for all but finitely many inputs x. We call t a name for the complexity class . Suppose we allow our machines to run longer, say h(x, t(x)) steps on argument x, where h is some fixed recursive function. One might expect that, for large enough h, permitting our machines to run longer by an amount h will always allow us to compute new functions, i.e., is a proper subset of . This turns out not to be the case: The “gap theorem” ([2], [3]) implies that for every recursive h there exists a recursive t such that . However, if we restrict our attention to names from a certain subclass of the recursive functions, then we can indeed uniformly increase the size of our -classes. Informally, we call a recursive function t “honest” if some machine computes t(x) in roughly t(x) steps for each argument x. (A precise definition is given in Definition 1 below.) Then according to the “compression theorem” [1], there exists a single recursive function h such that, for every honest t, is a proper subset of . Thus the phenomenon of the gap theorem is avoided by restricting attention to honest functions. It is a surprising consequence of the “honesty theorem” of McCreight and Meyer ([4], [5]) that there is no loss of generality in this restriction. Namely, for any recursive function t there is an honest recursive function t′ such that .

It has been known for some time that there is a primitive recursive permutation of the nonnegative integers whose inverse is recursive but not primitive recursive. For example one has this result apparently for the first time in Kuznecov [1] and implicitly in Kent [2] or J. Robinson [3], who shows that every singularly recursive function ƒ is representable aswhere A, B, C are primitive recursive and B is a permutation.