Papers
2010

On \( n \)tardy sets Submitted, page 38, 2010.
Harrington and Soare introduced the notion of an \( n \)tardy set. They showed that there is a nonempty \( \mathcal{E} \) property \( Q(A) \) such that if \( Q(A) \) then \( A \) is \( 2 \)tardy. Since they also showed no \( 2 \)tardy set is complete, Harrington and Soare showed that there exists an orbit of computably enumerable sets such that every set in that orbit is incomplete. Our study of \( n \)tardy sets takes off from where Harrington and Soare left off. We answer all the open questions asked by Harrington and Soare about \( n \)tardy sets. We show there is a \( 3 \)tardy set \( A \) which is not computed by any \( 2 \)tardy set \( B \). We also show that there are nonempty \( \mathcal{E} \) properties \( Q_n(A) \) such that if \( Q_n(A) \) then \( A \) is properly \( n \)tardy.@article{onntardysets,
author = {Cholak, Peter and Gerdes, Peter and Lange, Karen},title = {On {\( n \)}Tardy Sets},journal = {Submitted},pages = {38},year = {2010},} 
A \( \omega \)rea set forming a minimal pair with 0' Submitted, page 11, 2010. (arxiv preprint)
It is easy to see that no nREA set can form a (nontrivial) minimal pair with 0' and only slightly more difficult to observe that no wREA set can form a (nontrivial) minimal pair with 0". Shore has asked whether this can be improved to show that no wREA set forms a (nontrivial) minimal pair with 0'. We show that no such improvement is possible by constructing a noncomputable set C computable from 0" forming a minimal pair with 0'. We then show that no \alpha REA set can form a (nontrivial) minimal pair with 0".@article{omegaREAminimalpairzerojump,
author = {Gerdes, Peter M.},title = {A \( \omega \)REA Set Forming A Minimal Pair With \( 0' \)},journal = {Submitted},pages = {11},year = {2010},howpublished = {Submitted},} 
Harrington's solution to McLaughlin's conjecture and nonuniform selfmoduli Submitted, page 27, 2010. (arxiv preprint)
While much work has been done to characterize the Turing degrees computing members of various collections of fast growing functions, much less has been done to characterize the rate of growth necessary to compute particular degrees. Prior work has shown that every degree computed by all sufficiently fast growing functions is uniformly computed by all sufficiently fast growing functions. We show that the rate of growth sufficient for a function to uniformly compute a given Turing degree can be separated by an arbitrary number of jumps from the rate of growth that suffices for a function to nonuniformly compute the degree. These results use the unpublished method Harrington developed to answer McLaughlin's conjecture so we begin the paper with a rigorous presentation of the approach Harrington sketched in his handwritten notes on the conjecture. We also provide proofs for the important computability theoretic results Harrington noted were corollaries of this approach. In particular we provide the first published proof of Harrington's result that there is an effectively given sequence of \( \Pi^0_1 \) singletons that are \( Low_\alpha \) none of which is computable in the effective join of the \( \alpha \) jumps of the others for every computable ordinal \( \alpha \).@article{PMG:McLaughlin,
author = {Gerdes, Peter M.},title = {{H}arrington's Solution to {McLaughlin's} Conjecture and Nonuniform Selfmoduli},journal = {Submitted},pages = {27},year = {2010},}
2008

Moduli of Computation. Ph.D. in logic and the methodology of science, University of California, Berkeley, Fall 2008.
The relation between a functions rate of growth and it's computational properties is a traditional, and well studied, problem in computability theory. However, this relationship has been almost exclusively studied in a somewhat piecemeal fashion by fixing some notion of a fast growing function and classifying the degrees of those functions. Making use of the notion of a modulus of computation, a measure of the rate of growth sufficent to compute a given set, as introduced by Groszek and Slaman we explore the connection between rate of growth and Turing degree in a more general setting. In particular we do this by focusing on two particular types of moduli: the selfmoduli (those functions computable from any faster growing function) and the uniform moduli (functions witnessing a rate of growth sufficent to guarantee uniform computation by larger functions). After exploring the behavior of these objects we characterize the uniform selfmoduli and extend this characterization to sets with uniform moduli and in so doing answer a question of Groszek and Slaman. Finally we demonstrate that there are examples of selfmoduli that are very nonuniform.@phdthesis{moduliofcomputation,
author = {Gerdes, Peter Michael},title = {Moduli of Computation},type = {{Ph.D.} in Logic and the Methodology of Science},month = {Fall},year = {2008},school = {University of California, Berkeley},}
2001

Computably enumerable equivalence relations Studia Logica, 67(1):27–59, February 2001. ISSN 00393215. DOI: 10.1023/A:1010521410739
{We study computably enumerable equivalence relations (ceers) on N and unravel a rich structural theory for a strong notion of reducibility among ceers.}@article{CEER,
author = {Gao, Su and Gerdes, Peter M.},title = {Computably Enumerable Equivalence Relations},journal = {Studia Logica},volume = {67},number = {1},pages = {2759},month = feb,year = {2001},issn = {00393215},}
Talks
 A wREA Set Forming A Minimal Pair With 0', September 2010, Midwest Computability Seminar.
 nTardy Sets, July 2009, Computability in Europe.
 Computable in Every Majorizing Function, November 2008, Midwest Computability Seminar.
 Uniformly Computable in Every Faster Growing Function, October 2008, AMS Eastern Sectional.
 Sets With A NonUniform SelfModulus, January 2008, AMS/ASL Winter Meeting. (abstract, slides)
 Sets With A SelfModulus Bounding No NonRecursive \( \Delta^0_{\alpha} \) Set, 8th Graduate Student Conference in Logic. (abstract, slides)
 Comments in response to Belief and Beyond: Toward a New Orientation in Epistemology, May 2005, Formal Epistemology Workshop.
Misc
 Research Description (pdf)