Denis R. Hirschfeldt's Papers


Expository Papers

Calibrating randomness (with Rod Downey, André Nies, and Sebastiaan A. Terwijn)

Slicing the truth: on the computability theoretic and reverse mathematical analysis of combinatorial principles

Some questions in computable mathematics

Five papers on reverse mathematics and Ramsey-theoretic principles

Algorithmic randomness (with Rod Downey)

Computability and randomness (with Rod Downey)


Algorithmic Randomness and Dimension

Randomness, computability, and density (with Rod Downey and André Nies)

Randomness and reducibility (with Rod Downey and Geoff LaForte)

Trivial reals (with Rod Downey, André Nies, and Frank Stephan)

Using random sets as oracles (with André Nies and Frank Stephan)

Relativizing Chaitin's halting probability (with Rod Downey, Joseph S. Miller, and André Nies)

Limit computability and constructive measure (with Sebastiaan A. Terwijn)

Undecidability of the structure of the Solovay degrees of c.e. reals (with Rod Downey and Geoff LaForte)

Characterizing the strongly jump-traceable sets via randomness (with Noam Greenberg and André Nies)

Counting the changes of random Δ⁰₂ sets (with Santiago Figueira, Joseph S. Miller, Keng Meng Ng, and André Nies)

Finite self-information (with Rebecca Weber)


Reverse Mathematics and Computable Mathematics

A Δ⁰₂ set with no infinite low subset in either it or its complement (with Rod Downey, Steffen Lempp, and Reed Solomon)

Computability-theoretic and proof-theoretic aspects of partial and linear orderings (with Rod Downey, Steffen Lempp, and Reed Solomon)

Reverse mathematics of the Nielsen-Schreier theorem (with Rod Downey, Steffen Lempp, and Reed Solomon)

The strength of some combinatorial principles related to Ramsey's Theorem for pairs (with Carl G. Jockusch, Jr., Bjorn Kjos-Hanssen, Steffen Lempp, and Theodore A. Slaman)

Combinatorial principles weaker than Ramsey's Theorem for pairs (with Richard A. Shore)

Subspaces of computable vector spaces (with Rod Downey, Asher M. Kach, Steffen Lempp, Joseph R. Mileti, and Antonio Montalbán)

The Atomic Model Theorem and type omitting (with Richard A. Shore and Theodore A. Slaman)

Induction, bounding, weak combinatorial principles, and the Homogeneous Model Theorem (with Karen Lange and Richard A. Shore)

On notions of computability-theoretic reduction between Π¹₂ principles (with Carl G. Jockusch, Jr.)

The reverse mathematics of Hindman's Theorem for sums of exactly two elements (with Barbara F. Csima, Damir D. Dzhafarov, Carl G. Jockusch, Jr., Reed Solomon, and Linda Brown Westrick)

Ramsey's Theorem and products in the Weihrauch degrees (with Damir D. Dzhafarov, Jun Le Goh, Ludovic Patey, and Arno Pauly)

Combinatorial principles equivalent to weak induction (with Caleb Davis, Jeffry L. Hirst, Jake Pardo, Arno Pauly, and Keita Yokoyama)

Some results concerning the SRT²₂ vs. COH problem (with Peter A. Cholak, Damir D. Dzhafarov, and Ludovic Patey)

Reduction games, provability, and compactness (with Damir D. Dzhafarov and Sarah C. Reitzes)

Thin set versions of Hindman's Theorem (with Sarah C. Reitzes)


Computable Model Theory

Degree spectra of intrinsically c.e. relations

Degree spectra of relations on computable structures (doctoral dissertation)

Degree spectra of relations on computable structures (research communication)

Prime models of theories of computable linear orderings

Degree spectra of relations on computable structures in the presence of Δ⁰₂ isomorphisms

Degree spectra of relations on structures of finite computable dimension

Degree spectra and computable dimensions in algebraic structures (with Bakhadyr Khoussainov, Richard A. Shore, and Arkadii M. Slinko)

Uniformity in computable structure theory (with Rod Downey and Bakhadyr Khoussainov)

Degree spectra of relations on Boolean algebras (with Rod Downey and Sergey S. Goncharov)

A computably categorical structure whose expansion by a constant has infinite computable dimension (with Bakhadyr Khoussainov and Richard A. Shore)

Realizing levels of the hyperarithmetic hierarchy as degree spectra of relations on computable structures (with Walker M. White)

Bounding prime models (with Barbara F. Csima, Julia F. Knight, and Robert I. Soare)

Computable trees, prime models, and relative decidability

An uncountably categorical theory whose only computably presentable model is saturated (with Bakhadyr Khoussainov and Pavel Semukhin)

Bounding homogeneous models (with Barbara F. Csima, Valentina S. Harizanov, and Robert I. Soare)

Π⁰₁ classes and strong degree spectra of relations (with John Chisholm, Jennifer Chubb, Valentina S. Harizanov, Carl G. Jockusch, Jr., Timothy McNicholl, and Sarah Pingrey)

Order-computable sets (with Russell Miller and Sergei Podzorov)

Categoricity properties for computable algebraic fields (with Ken Kramer, Russell Miller, and Alexandra Shlapentokh)

On finitely presented expansions of computably enumerable semigroups (with Bakhadyr Khoussainov)


Notions of Approximate Computability

Asymptotic density and the coarse computability bound (with Carl G. Jockusch, Jr., Timothy H. McNicholl, and Paul E. Schupp)

Coarse reducibility and algorithmic randomness (with Carl G. Jockusch, Jr., Rutger Kuyper, and Paul E. Schupp)

Dense computability, upper cones, and minimal pairs (with Eric P. Astor and Carl G. Jockusch, Jr.)

A minimal pair in the generic degrees

Coarse computability, the density metric, Hausdorff distances between Turing degrees, perfect trees, and reverse mathematics (with Carl G. Jockusch, Jr. and Paul E. Schupp)


Degree Theory

Undecidability and 1-types in intervals of the computably enumerable degrees (with Klaus Ambos-Spies and Richard A. Shore)

Every 1-generic computes a properly 1-generic (with Barbara F. Csima, Rod Downey, Noam Greenberg, and Joseph S. Miller)

A Feiner look at the intermediate degrees (with Asher M. Kach and Antonio Montalbán)