20 found
Order:
  1.  16
    Anti-Mitotic Recursively Enumerable Sets.Klaus Ambos-Spies - 1985 - Zeitschrift fur mathematische Logik und Grundlagen der Mathematik 31 (29-30):461-477.
    Direct download (2 more)  
     
    Export citation  
     
    My bibliography   9 citations  
  2.  7
    Undecidability and 1-Types in the Recursively Enumerable Degrees.Klaus Ambos-Spies & Richard A. Shore - 1993 - Annals of Pure and Applied Logic 63 (1):3-37.
    Ambos-Spies, K. and R.A. Shore, Undecidability and 1-types in the recursively enumerable degrees, Annals of Pure and Applied Logic 63 3–37. We show that the theory of the partial ordering of recursively enumerable Turing degrees is undecidable and has uncountably many 1-types. In contrast to the original proof of the former which used a very complicated O''' argument our proof proceeds by a much simpler infinite injury argument. Moreover, it combines with the permitting technique to get similar results for any (...)
    Direct download (3 more)  
     
    Export citation  
     
    My bibliography   7 citations  
  3.  18
    The Theory of the Recursively Enumerable Weak Truth-Table Degrees is Undecidable.Klaus Ambos-Spies, André Nies & Richard A. Shore - 1992 - Journal of Symbolic Logic 57 (3):864-874.
    We show that the partial order of Σ0 3-sets under inclusion is elementarily definable with parameters in the semilattice of r.e. wtt-degrees. Using a result of E. Herrmann, we can deduce that this semilattice has an undecidable theory, thereby solving an open problem of P. Odifreddi.
    Direct download (7 more)  
     
    Export citation  
     
    My bibliography   7 citations  
  4.  2
    The Recursively Enumerable Degrees Have Infinitely Many One-Types.Klaus Ambos-Spies & Robert I. Soare - 1989 - Annals of Pure and Applied Logic 44 (1-2):1-23.
  5.  8
    Bounding Non- GL ₂ and R.E.A.Klaus Ambos-Spies, Decheng Ding, Wei Wang & Liang Yu - 2009 - Journal of Symbolic Logic 74 (3):989-1000.
    We prove that every Turing degree a bounding some non-GL₂ degree is recursively enumerable in and above (r.e.a.) some 1-generic degree.
    Direct download (5 more)  
     
    Export citation  
     
    My bibliography   2 citations  
  6.  11
    Degree Theoretical Splitting Properties of Recursively Enumerable Sets.Klaus Ambos-Spies & Peter A. Fejer - 1988 - Journal of Symbolic Logic 53 (4):1110-1137.
    Direct download (7 more)  
     
    Export citation  
     
    My bibliography   5 citations  
  7.  11
    An Extension of the Nondiamond Theorem in Classical and Α-Recursion Theory.Klaus Ambos-Spies - 1984 - Journal of Symbolic Logic 49 (2):586-607.
    Direct download (7 more)  
     
    Export citation  
     
    My bibliography   4 citations  
  8.  17
    Decidability of the Two-Quantifier Theory of the Recursively Enumerable Weak Truth-Table Degrees and Other Distributive Upper Semi-Lattices.Klaus Ambos-Spies, Peter A. Fejer, Steffen Lempp & Manuel Lerman - 1996 - Journal of Symbolic Logic 61 (3):880-905.
    We give a decision procedure for the ∀∃-theory of the weak truth-table (wtt) degrees of the recursively enumerable sets. The key to this decision procedure is a characterization of the finite lattices which can be embedded into the r.e. wtt-degrees by a map which preserves the least and greatest elements: a finite lattice has such an embedding if and only if it is distributive and the ideal generated by its cappable elements and the filter generated by its cuppable elements are (...)
    Direct download (9 more)  
     
    Export citation  
     
    My bibliography   2 citations  
  9.  5
    Comparing DNR and WWKL.Klaus Ambos-Spies, Bjørn Kjos-Hanssen, Steffen Lempp & Theodore Slaman - 2004 - Journal of Symbolic Logic 69 (4):1089-1104.
    In Reverse Mathematics, the axiom system DNR, asserting the existence of diagonally non-recursive functions, is strictly weaker than WWKL0.
    Direct download (5 more)  
     
    Export citation  
     
    My bibliography   1 citation  
  10.  3
    The Continuity of Cupping to 0'.Klaus Ambos-Spies, Alistair H. Lachlan & Robert I. Soare - 1993 - Annals of Pure and Applied Logic 64 (3):195-209.
    It is shown that, if a, b are recursively enumerable degrees such that 0
    Direct download (3 more)  
     
    Export citation  
     
    My bibliography   2 citations  
  11.  6
    Cappable Recursively Enumerable Degrees and Post's Program.Klaus Ambos-Spies & André Nies - 1992 - Archive for Mathematical Logic 32 (1):51-56.
    We give a simple structural property which characterizes the r.e. sets whose (Turing) degrees are cappable. Since cappable degrees are incomplete, this may be viewed as a solution of Post's program, which asks for a simple structural property of nonrecursive r.e. sets which ensures incompleteness.
    Direct download (3 more)  
     
    Export citation  
     
    My bibliography   1 citation  
  12.  10
    Cupping and Noncapping in the Re Weak Truth Table and Turing Degrees.Klaus Ambos-Spies - 1985 - Archive for Mathematical Logic 25 (1):109-126.
  13.  5
    Preface.Klaus Ambos-Spies, Joan Bagaria, Enrique Casanovas & Ulrich Kohlenbach - 2013 - Annals of Pure and Applied Logic 164 (12):1177.
  14.  7
    Preface.Klaus Ambos-Spies, Theodore A. Slaman & Robert I. Soare - 1998 - Annals of Pure and Applied Logic 94 (1-3):1.
  15.  6
    The Partial Orderings of the Computably Enumerable ibT-Degrees and Cl-Degrees Are Not Elementarily Equivalent.Klaus Ambos-Spies, Philipp Bodewig, Yun Fan & Thorsten Kräling - 2013 - Annals of Pure and Applied Logic 164 (5):577-588.
    We show that, in the partial ordering of the computably enumerable computable Lipschitz degrees, there is a degree a>0a>0 such that the class of the degrees which do not cup to a is not bounded by any degree less than a. Since Ambos-Spies [1] has shown that, in the partial ordering of the c.e. identity-bounded Turing degrees, for any degree a>0a>0 the degrees which do not cup to a are bounded by the 1-shift a+1a+1 of a where a+1 (...)
    Direct download (3 more)  
     
    Export citation  
     
    My bibliography  
  16.  6
    Embeddings of N5 and the Contiguous Degrees.Klaus Ambos-Spies & Peter A. Fejer - 2001 - Annals of Pure and Applied Logic 112 (2-3):151-188.
    Downey and Lempp 1215–1240) have shown that the contiguous computably enumerable degrees, i.e. the c.e. Turing degrees containing only one c.e. weak truth-table degree, can be characterized by a local distributivity property. Here we extend their result by showing that a c.e. degree a is noncontiguous if and only if there is an embedding of the nonmodular 5-element lattice N5 into the c.e. degrees which maps the top to the degree a. In particular, this shows that local nondistributivity coincides with (...)
    Direct download (3 more)  
     
    Export citation  
     
    My bibliography  
  17.  3
    Computability in Europe 2009.Klaus Ambos-Spies, Arnold Beckmann, Samuel R. Buss & Benedikt Löwe - 2012 - Annals of Pure and Applied Logic 163 (5):483-484.
    Direct download (2 more)  
     
    Export citation  
     
    My bibliography  
  18.  1
    On the Strongly Bounded Turing Degrees of Simple Sets.Klaus Ambos-Spies - 2014 - In Dieter Spreen, Hannes Diener & Vasco Brattka (eds.), Logic, Computation, Hierarchies. De Gruyter. pp. 23-78.
  19.  1
    Participants and Titles of Lectures.Klaus Ambos-Spies, Marat Arslanov, Douglas Cenzer, Peter Cholak, Chi Tat Chong, Decheng Ding, Rod Downey, Peter A. Fejer, Sergei S. Goncharov & Edward R. Griffor - 1998 - Annals of Pure and Applied Logic 94 (1):3-6.
    No categories
    Direct download  
     
    Export citation  
     
    My bibliography  
  20. Undecidability and 1-Types in Intervals of the Computably Enumerable Degrees.Klaus Ambos-Spies, Denis R. Hirschfeldt & Richard A. Shore - 2000 - Annals of Pure and Applied Logic 106 (1-3):1-47.
    We show that the theory of the partial ordering of the computably enumerable degrees in any given nontrivial interval is undecidable and has uncountably many 1-types.
    Direct download (3 more)  
     
    Export citation  
     
    My bibliography