Intrinsic Complexity of Recursive Functions on Natural Numbers with Standard Order

Nikolay Bazhenov, Dariusz Kalocinski, Michal Wroclawski

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 x is 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

Abstract

The intrinsic complexity of a relation on a given computable structure is captured by the notion of its degree spectrum - the set of Turing degrees of images of the relation in all computable isomorphic copies of that structure. We investigate the intrinsic complexity of unary total recursive functions on nonnegative integers with standard order. According to existing results, the possible spectra of such functions include three sets consisting of precisely: the computable degree, all c.e. degrees and all Δ₂ degrees. These results, however, fall far short of the full classification. In this paper, we obtain a more complete picture by giving a few criteria for a function to have intrinsic complexity equal to one of the three candidate sets of degrees. Our investigations are based on the notion of block functions and a broader class of quasi-block functions beyond which all functions of interest have intrinsic complexity equal to the c.e. degrees. We also answer the questions raised by Wright [Wright, 2018] and Harrison-Trainor [Harrison-Trainor, 2018] by showing that the division between computable, c.e. and Δ₂ degrees is insufficient in this context as there is a unary total recursive function whose spectrum contains all c.e. degrees but is strictly contained in the Δ₂ degrees.
BibTeX
@inproceedings{bazhenov2022intrinsic,
  author = {Nikolay Bazhenov and Dariusz Kalocinski and Michal Wroclawski},
  title = {{Intrinsic Complexity of Recursive Functions on Natural Numbers with Standard Order}},
  booktitle = {STACS},
  year = {2022},
  doi = {10.4230/lipics.stacs.2022.8},
}

Loading related content...

Figure