TL;DR
This paper delves into the "intrinsic complexity" of simple functions on natural numbers, specifically how complex they appear across different ways of representing those numbers. The authors introduce new structural properties of functions (block and quasi-block) to precisely characterize these complexities, revealing that the previously known categories (computable, c.e., and Δ₂) are insufficient, and demonstrating the existence of functions with "unusual" complexity spectra.
What Problem Does This Paper Address?
In computability theory, we often study the inherent complexity of mathematical objects. For relations on structures like the natural numbers with their standard order (w, <), this complexity can be measured by their "degree spectrum." This spectrum is the set of Turing degrees of the relation's images under all possible computable re-orderings (isomorphisms) of the structure. The question is: what are all the possible degree spectra for unary total recursive functions on (w, <)? Previous work established that these spectra could be the computable degree, all recursively enumerable (c.e.) degrees, or all Δ₂ degrees. However, this was far from a complete classification. This paper aims to provide a more detailed understanding by identifying specific function properties that lead to these spectra and, crucially, by showing that there are functions whose spectra fall between these established categories, answering open questions in the field.
Methods
The core of the paper's methodology lies in introducing and utilizing two key structural properties of functions:
- Block Functions: A function is a "block function" if every element is contained within a special kind of interval called an "f-block." An f-block is an interval that is "closed" under the function (meaning if
xis in the block,f(x)is also in the block, and importantly, the preimages of elements within the block are also contained within the block). - Quasi-Block Functions: This is a generalization of block functions. A function is a "quasi-block function" if there are arbitrarily long finite initial segments of natural numbers that are "closed" under the function.
The authors then develop sophisticated construction techniques, particularly a "pushing-to-the-right" (PtR) module, to build computable copies of (w, <) where the function's behavior (its image under the isomorphism) exhibits specific Turing degree properties. These constructions are carefully orchestrated to satisfy various requirements related to the function's structure and the desired Turing degree of its spectrum.
Datasets
Not discussed in the paper. The paper focuses on theoretical constructions and properties of computable functions rather than empirical evaluation on datasets.
Key Insights and Ideas
- Beyond the Big Three: The most striking insight is the demonstration that the computable, c.e., and Δ₂ degrees do not exhaust all possible spectra. The paper proves the existence of a function whose spectrum contains all c.e. degrees but is strictly contained within the Δ₂ degrees, answering a long-standing question.
- Structural Properties Matter: The introduction and analysis of "block" and "quasi-block" functions provide a powerful lens for understanding the relationship between a function's internal structure and its degree spectrum. Non-quasi-block functions have a predictable spectrum (all c.e. degrees), while block functions offer more variety.
- Fine-Grained Complexity: The paper shows that even within the Δ₂ degrees, there's room for "unusual" spectra, suggesting a more nuanced landscape of intrinsic complexity than previously understood.
- Sophisticated Construction Techniques: The development and application of the "pushing-to-the-right" module, along with careful management of "tickets" and "reservations," are crucial for constructing specific isomorphic copies of (w, <) that yield the desired degree spectra.
Key Results
- Characterization of Non-Quasi-Block Functions: Theorem 18 states that any unary total computable non-quasi-block function has a degree spectrum equal to the set of all c.e. degrees.
- Block Functions with Finitely Many Types: Theorem 14 shows that a computable block function with finitely many "f-types" (isomorphism types of its blocks) and that is not almost identity has a degree spectrum consisting of all Δ₂ degrees.
- Existence of Unusual Spectra: Theorem 23 proves the existence of a computable block function whose degree spectrum strictly contains all c.e. degrees but is strictly contained within the Δ₂ degrees. This is a major result that expands the known possibilities for intrinsic complexity.
Limitations and Future Work
- Exact Spectra of Unusual Cases: While Theorem 23 proves the existence of a function with an "unusual" spectrum, the paper notes that the exact contents of this spectrum are still unknown.
- Infinitely Many Spectra? The existence of an unusual spectrum leads to the hypothesis that there might be infinitely many such spectra for computable block functions.
- General Open Question: The paper concludes by posing the general question: "what are the possible kinds of nonstandard spectra of computable block functions on (w, <)?" This suggests a broad avenue for future research in characterizing the full range of intrinsic complexities.
Summary updated