2021

• 

  Uri Andrews, Peter M Gerdes, Steffen Lempp, Joseph S Miller, and Noah D Schweber. Computability and the Symmetric Difference Operator. Logic Journal of the IGPL, 06 2021. ISSN 1367-0751. jzab017.

  {Combinatorial operations on sets are almost never well defined on Turing degrees, a fact so obvious that counterexamples are worth exhibiting. The case we focus on is the symmetric-difference operator; there are pairs of (nonzero) degrees for which the symmetric-difference operation is well defined. Some examples can be extracted from the literature, e.g. from the existence of nonzero degrees with strong minimal covers. We focus on the case of incomparable r.e. degrees for which the symmetric-difference operation is well defined.}

  @article{computability-symetric-difference,
  

  author       = {Andrews, Uri and Gerdes, Peter M and Lempp, Steffen and Miller, Joseph S and Schweber, Noah D},

  title        = {{Computability and the Symmetric Difference Operator}},

  journal      = {Logic Journal of the IGPL},

  month        = {06},

  year         = {2021},

  issn         = {1367-0751},

  note         = {jzab017},

  }
• 

  Peter M. Gerdes and Peter A. Cholak. Extending Properly n-REA Sets. Under Review, 2021. arXiv: 2107.01299.

  In [5] Soare and Stob prove that if \$A\$ is an r.e. set which isn't computable then there is a set of the form \$A {\textbackslash}oplus W{\textasciicircum}A\_e\$ which isn't of r.e. Turing degree. If we define a properly \$n+1\$-REA set to be an \$n+1\$-REA set which isn't Turing equivalent to any \$n\$-REA set (and identify 0-REA sets with the computable sets) this result shows that every properly 1-REA set can be extended to a properly 2-REA set. This result was extended in [1] by Cholak and Hinman who proved that every 2-REA set can be extended to a properly 3-REA set. This leads naturally to the hypothesis that every properly \$n\$-REA set can be extended to a properly \$n+1\$-REA set. In this paper, we show this hypothesis is false and that there is a properly \$3\$-REA set which can't be extended to a properly \$4\$-REA set.

  @article{extending-properly-nREA,
  

  author       = {Gerdes, Peter M. and Cholak, Peter A.},

  title        = {Extending {Properly} n-{REA} {Sets}},

  journal      = {Under Review},

  year         = {2021},

  note         = {arXiv: 2107.01299},

  }

2020

• 

  Peter M. Gerdes. An \( ømega \)-rea set forming a minimal pair with \( 0' \). Computability, 9(1):37–50, January 2020. ISSN 2211-3568. Publisher: IOS Press.

  It is easy to see that no n-REA set can form a (non-trivial) minimal pair with 0' and only slightly more difficult to observe that no w-REA set can form a (non-trivial) minimal pair with 0". Shore has asked whether this can be improved to show that no w-REA set forms a (non-trivial) minimal pair with 0'. We show that no such improvement is possible by constructing a non-computable set C computable from 0" forming a minimal pair with 0'. We then show that no \alpha -REA set can form a (non-trivial) minimal pair with 0".

  @article{omega-REA-minimal-pair-zero-jump,
  

  author       = {Gerdes, Peter M.},

  title        = {An \( \omega \)-REA Set Forming A Minimal Pair With \( 0' \)},

  journal      = {Computability},

  volume       = {9},

  number       = {1},

  pages        = {37--50},

  month        = jan,

  year         = {2020},

  issn         = {2211-3568},

  note         = {Publisher: IOS Press},

  }

2014

• 

  Uri Andrews, Peter Gerdes, and Joseph S. Miller. The degrees of bi-hyperhyperimmune sets. Annals of Pure and Applied Logic, 165(3):803–811, March 2014. ISSN 0168-0072.

  We study the degrees of bi-hyperhyperimmune (bi-hhi) sets. Our main result characterizes these degrees as those that compute a function that is not dominated by any Δ20 function, and equivalently, those that compute a weak 2-generic. These characterizations imply that the collection of bi-hhi Turing degrees is closed upwards.

  @article{bihhi-degrees,
  

  author       = {Andrews, Uri and Gerdes, Peter and Miller, Joseph S.},

  title        = {The degrees of bi-hyperhyperimmune sets},

  journal      = {Annals of Pure and Applied Logic},

  volume       = {165},

  number       = {3},

  pages        = {803--811},

  month        = mar,

  year         = {2014},

  issn         = {0168-0072},

  }

2012

• Peter Cholak, Peter Gerdes, and Karen Lange. On $n$-tardy sets. Ann. Pure Appl. Log., 163:1252–1270, 2012.

  @article{on-n-tardy-sets,
  

  author       = {Cholak, Peter and Gerdes, Peter and Lange, Karen},

  title        = {On {$n$}-Tardy Sets},

  journal      = {Ann. Pure Appl. Log.},

  volume       = {163},

  pages        = {1252-1270},

  year         = {2012},

  }

2010

• 

  Peter M. Gerdes. Harrington's solution to McLaughlin's conjecture and non-uniform self-moduli. Unpublished, page 27, 2010.

  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 non-uniformly 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 Non-uniform Self-moduli},

  journal      = {Unpublished},

  pages        = {27},

  year         = {2010},

  }

2008

• 

  Peter Michael Gerdes. 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 self-moduli (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 self-moduli 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 self-moduli that are very non-uniform.

  @phdthesis{moduli-of-computation,
  

  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

• 

  Su Gao and Peter M. Gerdes. Computably enumerable equivalence relations. Studia Logica, 67(1):27–59, February 2001. ISSN 0039-3215.

  {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        = {27--59},

  month        = feb,

  year         = {2001},

  issn         = {0039-3215},

  }