---
abstract: |
    It is a basic fact that, given a computer language and a computable integer function, there exists a shortest program in that language which computes the desired function. Once a programmer establishes the correctness of a program, she then need only verify that the program is the shortest possible in order to declare complete victory. Unfortunately, she can't. A creature that could identify minimal programs would not only be able to decide the halting problem, but she could even decide the halting problem for machines with halting set oracles. Such a creature exceeds the powers of ordinary machine cognition, and must therefore be a divine jument-numen.

    Suppose, however, the programmer would be satisfied to know just whether or not her program is minimal up to finitely many errors. In this case, even the jument-numen is helpless: something much stronger is needed. Just as we can associate equality with the ordinary notion of "minimal," we can associate an equivalence relation, $=^*$, with the principle of "minimal up to finitely many errors." This thesis is the first to explore the extensive realm of minimal indices beyond the $=^*$ relation. Every equivalence relation gives rise to a notion of minimality, modulo that relation. We call the resulting collection of minimal indices a *spectral set*, because it selects exactly one function from each equivalence class. Spectral sets are rare, natural examples of non-index sets which are neither $\Sigma_n$ nor $\Pi_n$-complete.

    In this thesis, we classify spectral sets according to their thinness and information content. We give optimal immunity results for the spectral sets (that is, we identify types of sets which are not contained in spectral sets), and we place these sets in the arithmetic hierarchy (which quantitatively measures their information contents). Some lower bounds in the arithmetic hierarchy follow from immunity properties alone, but we further refine these immunity bounds using direct techniques. We also measure information content with Turing equivalences. In fact, the spectral sets become canonical iterations of the halting set when we list our computer programs in the right order. Regardless of the particular numbering, a reasonable amount of information is always present in such sets.

    We now informally describe the contents of some spectral sets. The $\Pi_3$-Separation Theorem says that the spectral sets pertaining to $\equiv_1$, $=^*$, and $\equiv_{\mathrm{m}}$ each have the same complexity with respect to the arithmetic hierarchy, yet each of these sets is immune against a different level of the arithmetic hierarchy. We can thus quantitatively compare the strength of equivalence relations by way of immunity. We also prove a result which we call the Forcing Lowness Lemma. Using this lemma, we show that ${\emptyset}''''$ is decidable in ${\mathrm{MIN}}^{\mathrm{T}}$ (the spectral set for $\equiv_{\mathrm{T}}$) together with ${\emptyset}''$. This result is probably optimal, and we apply the Forcing Lowness Lemma again to show that, in some formal sense, this fact will be difficult to prove.

    Armed with this new machinery, we highlight its utility with some new applications. First, we prove the Peak Hierarchy Theorem: there exists a set which neither contains nor is disjoint from any infinite arithmetic set, yet the set is majorized by a computable function. Furthermore, the set that we construct is natural in the sense that it contains a spectral set. Along the way, we construct a computable sequence of c.e$.$ sets in which no set can be computed from the join of the others, for any iteration of the jump operator.

    We use the machinery of spectral sets to quantitatively compare the power of nondeterminism with the power of the jump operator. We show that in the world of computably enumerable sets, nondeterminism contributes nothing to immunity. In this respect, the jump operator outshines nondeterminism. Nonetheless, we can ascend naturally from the lowest level of the spectral hierarchy using nondeterminism.

    Finally, we present connections to the Arslanov Completeness Criterion which stand as immediate consequences of immunity properties for spectral sets.
author:
- Jason Teutsch
bibliography:
- 'spectral.bib'
title: Noncomputable Spectral Sets
---

For my Mama, whose \*-minimal index is computable (because it's finite).

Love the Ma.

It seems nothing short of a miracle that I now find myself in a position to graduate with a doctorate in mathematics. This thesis is the product of contributions from a few outstanding individuals that I've known (in the biblical sense) along my academic path. Without the personal connections that I am about to mention, there would indeed be no work here to acknowledge.

In the summer of 2004, I showed up on Lance Fortnow's doorstep in Chicago, poised to learn something about computer science. Not only did Lance *not* send me home (which would have been impossible anyway, since I didn't come from anywhere), he completely encouraged me to learn. Lance dedicated enormous time and energy to helping me achieve excellence in my research. Not only did he provide me with invaluable guidance and fill me with enthusiasm for my academic work, but in a formal sense, he allowed me to continue my studies by taking me on as a PhD student. When people read this PhD dissertation a hundred years from now, Lance Fortnow will undoubtedly be remembered for his outstanding research contributions to the field of theoretical computer science. But in 2107, this thesis will also remind readers that Lance is an exceptional mentor who showed exceeding kindness towards strangers. His efforts have made all the difference. Thanks for taking a chance on me.

I would like to thank the faculty, staff, and administration at University of Chicago and its Computer Science Department, as well as the affiliates of the Committee on Institutional Cooperation for providing me with all of the resources I needed to complete a research dissertation in mathematics during these past two years. Not only have these institutions provided me with access to an exceptional educational opportunities in theoretical computer science, but they also helped me to formally complete the degree requirements at my home institution. Even though I was never a degree student at University of Chicago, I've always felt like family.

Thanks to my mom and dad, who provided me with support when my home institution wasn't able to. In 2004, my parents gave me a place to live, a lot of tasty food, and a bit of encouragement when I really needed it.

Thanks to Professor William Ziemer and Chunlai Zhou, who together taught me the love of mathematical analysis early on in my graduate career. Chunlai, in particular, has been a most insightful study companion. His contagious commitment to learning surely contributed to my passing grades on the math qualifying exams during my first year of graduate school.

Inspiration for this project came from Marcus Schaefer, Robert Soare, and Joe Miller. Marcus Schaefer invented the tantalizing ${\mathrm{MIN}}^*$ problem, the catalyst for this entire work. Robert Soare not only invited me to his enlightening computability theory class this year, but he also shared some technical suggestions which gave me confidence to prove a couple of the hard theorems in this thesis. In 2003, I first experienced computability theory during Joe Miller's office hours for Recursion Theory. Although I had a scheduling conflict which prevented me from ever attending his lectures, I discovered the beautiful nature of computability theory outside of class time, thanks to the instructor's patience and enthusiasm.

Thanks to Kevin Zumbrun and Misty Cummings at Indiana University, whose efforts ultimately assembled the bureaucratic pieces of my academic career and allowed me to earn a doctorate in mathematics. For his contributions as a mentor, I'd also like to thank Larry Moss, who would have been on my dissertation committee had he not moved to Africa this year.

Finally, I would like to acknowledge my colleagues at University of Chicago, especially Parinya Chalermsook and Raghav Kulkarni, who introduced me to the field of computer science. And Gabriela Turcu, who went ice skating with me sometimes.

Goodnight, and g-d bless America.

{'source': 'arXiv_out/math0701904_extract_spectral'}