Computability · 2012 · 35 citations · 12 references
Natural SciencesComputer ScienceMathematicsNumber TheorySet TheoryTheory Of ComputationAxiomatic Set TheoryComputability TheorySet SystemsStructural ComplexityBorel HierarchyComputable ReducibilityComputable Structure TheoryDescriptive Set-theoretic ComplexityGraph IsomorphismOpen QuestionsReducibilityTuring Reducibility
The notion of computable reducibility between equivalence relations on the natural numbers provides a natural computable analogue of Borel reducibility. We investigate the computable reducibility hierarchy, comparing and contrasting it with the Borel
12
Recursively enumerable sets and degrees
Robert I. Soare · Bulletin of the American Mathematical Society · 1978 · 1.6K citations · Full text
Comparing Classes of Finite Structures
Wesley Calvert, Desmond Cummins, Julia F. Knight et al. · Algebra and Logic · 2004 · 72 citations
Computably Enumerable Equivalence Relations
Peter Gerdes · Studia Logica · 2001 · 72 citations · Full text