Switch to: References

Citations of:

Recursion theory

Providence, R.I.: American Mathematical Society (1985)

Add citations

You must login to add citations.
  1. Effectively inseparable Boolean algebras in lattices of sentences.V. Yu Shavrukov - 2010 - Archive for Mathematical Logic 49 (1):69-89.
    We show the non-arithmeticity of 1st order theories of lattices of Σ n sentences modulo provable equivalence in a formal theory, of diagonalizable algebras of a wider class of arithmetic theories than has been previously known, and of the lattice of degrees of interpretability over PA. The first two results are applications of Nies’ theorem on the non-arithmeticity of the 1st order theory of the lattice of r.e. ideals on any effectively dense r.e. Boolean algebra. The theorem on degrees of (...)
    Download  
     
    Export citation  
     
    Bookmark   5 citations  
  • Recursively Enumerable Equivalence Relations Modulo Finite Differences.André Nies - 1994 - Mathematical Logic Quarterly 40 (4):490-518.
    We investigate the upper semilattice Eq* of recursively enumerable equivalence relations modulo finite differences. Several natural subclasses are shown to be first-order definable in Eq*. Building on this we define a copy of the structure of recursively enumerable many-one degrees in Eq*, thereby showing that Th has the same computational complexity as the true first-order arithmetic.
    Download  
     
    Export citation  
     
    Bookmark   5 citations  
  • (1 other version)Automorphisms and Recursive Structures.R. G. Downey & J. B. Remmel - 1987 - Zeitschrift fur mathematische Logik und Grundlagen der Mathematik 33 (4):339-345.
    Download  
     
    Export citation  
     
    Bookmark  
  • Recursive versus recursively enumerable binary relations.Dev K. Roy - 1993 - Studia Logica 52 (4):587 - 593.
    The properties of antisymmetry and linearity are easily seen to be sufficient for a recursively enumerable binary relation to be recursively isomorphic to a recursive relation. Removing either condition allows for the existence of a structure where no recursive isomorph exists, and natural examples of such structures are surveyed.
    Download  
     
    Export citation  
     
    Bookmark  
  • (1 other version)Automorphisms and Recursive Structures.R. G. Downey & J. B. Remmel - 1987 - Mathematical Logic Quarterly 33 (4):339-345.
    Download  
     
    Export citation  
     
    Bookmark  
  • Conjectures and questions from Gerald Sacks's Degrees of Unsolvability.Richard A. Shore - 1997 - Archive for Mathematical Logic 36 (4-5):233-253.
    We describe the important role that the conjectures and questions posed at the end of the two editions of Gerald Sacks's Degrees of Unsolvability have had in the development of recursion theory over the past thirty years.
    Download  
     
    Export citation  
     
    Bookmark   2 citations