Journal of Symbolic Logic · 2007 · 15 citations · 12 references
ComputingComputer ScienceMathematicsDiscrete MathematicsSet TheoryTheory Of ComputationCombinatorial Set TheoryComputability TheoryComputational ComplexitySet SystemsStructural ComplexityComputable Structure TheoryIndex SetsStructural Properties Of Complexity Classes
Abstract This paper calculates, in a precise way. the complexity of the index sets for three classes of computable structures: the class of structures of Scott rank , the class , of structures of Scott rank , and the class K of all structures of non-computable Scott rank. We show that I(K) is m -complete is m -complete relative to Kleene's and is m -complete relative to .
12
Theory of Recursive Functions and Effective Computability
D. C. Cooper · The Computer Journal · 1969 · 2.6K citations · Full text
Recursive pseudo-well-orderings
Transactions of the American Mathematical Society · 1968 · 119 citations · Full text
Computable Structure and Non-Structure Theorems
Julia F. Knight · Algebra and Logic · 2002 · 109 citations
Scott sentences and admissible sets
Mark Nadel · Annals of Mathematical Logic · 1974 · 76 citations