39 citations · 109 across the 22 of their papers we have counts for
24 papers
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 of is the set of all whose symmetric difference with has asymptotic density 0. There is a natural metric on the space $\mathcal{S}…
Asymptotic Density and the Theory of Computability: A partial survey
Carl G. Jockusch, Paul E. Schupp
In this article we survey the development of generic and coarse computability and the main results on how classical asymptotic density interacts with the theory of computability.
Computational complexity and the conjugacy problem
Alexei Miasnikov, Paul E. Schupp
The conjugacy problem for a finitely generated group is the two-variable problem of deciding for an arbitrary pair of elements of , whether or not is conjugate t…
Asymptotic density and the coarse computability bound
Denis R. Hirschfeldt, Carl G. Jockusch, Timothy H. McNicholl +1
For we say that a set is \emph{coarsely computable at density} if there is a computable set such that has lower density…
Coarse Reducibility and Algorithmic Randomness
Denis R. Hirschfeldt, Carl G. Jockusch, Rutger Kuyper +1
A coarse description of a subset A of omega is a subset D of omega such that the symmetric difference of A and D has asymptotic density 0. We study the extent to which noncomputabl…
Multipass automata and group word problems
Tullio Ceccherini-Silberstein, Michel Coornaert, Francesca Fiorenzi +2
We introduce the notion of multipass automata as a generalization of pushdown automata and study the classes of languages accepted by such machines. The class of languages accepted…