D. Hirschfeldt

activity

20152021

most citedAsymptotic density and the coarse computability bound

2 citations · 3 across the 4 of their papers we have counts for

collaborators

10 papers

math.LO2021

A Feiner Look at the Intermediate Degrees

Denis R. Hirschfeldt, Asher M. Kach, Antonio Montalbán

We say that a set $S$ is $Δ_{(n)}^{0} (X)$ if membership of $n$ in $S$ is a $Δ_{n}^{0} (X)$ question, uniformly in $n$ . A set $X$ is low for $Δ$ -Feiner if every set $S$ that is $Δ^0_{(n)…

math.LO2021★ 1 cited

Coarse computability, the density metric, Hausdorff distances between Turing degrees, perfect trees, and reverse mathematics

Denis R. Hirschfeldt, Carl G. Jockusch, Paul E. Schupp

The coarse similarity class $[A]$ of $A$ is the set of all $B$ whose symmetric difference with $A$ has asymptotic density 0. There is a natural metric $δ$ on the space $\mathcal{S}…

math.LO2019

A minimal pair in the generic degrees

Denis R. Hirschfeldt

We show that there is a minimal pair in the nonuniform generic degrees, and hence also in the uniform generic degrees. This fact contrasts with Igusa's result that there are no min…

math.LO2019

Some results concerning the $SRT_{2}^{2}$ vs. $COH$ problem

Peter A. Cholak, Damir D. Dzhafarov, Denis R. Hirschfeldt +1

The $SRT_{2}^{2}$ vs.\ $COH$ problem is a central problem in computable combinatorics and reverse mathematics, asking whether every Turing ideal that satisfies the pr…

math.LO2018

Combinatorial principles equivalent to weak induction

Caleb Davis, Denis R. Hirschfeldt, Jeffry L. Hirst +3

We consider two combinatorial principles, $ERT$ and $ECT$ . Both are easily proved in $RCA_{0}$ plus $Σ_{2}^{0}$ induction. We give two proofs of $ERT$ in ${…

math.LO2018

Dense computability, upper cones, and minimal pairs

Eric P. Astor, Denis R. Hirschfeldt, Carl G. Jockusch

This paper concerns algorithms that give correct answers with (asymptotic) density $1$ . A dense description of a function $g : ω \to ω$ is a partial function $f$ on $ω$ such that $\…