Switch to: References

Add citations

You must login to add citations.
  1. Benign Cost Functions and Lowness Properties.Noam Greenberg & André Nies - 2011 - Journal of Symbolic Logic 76 (1):289 - 312.
    We show that the class of strongly jump-traceable c.e. sets can be characterised as those which have sufficiently slow enumerations so they obey a class of well-behaved cost functions, called benign. This characterisation implies the containment of the class of strongly jump-traceable c.e. Turing degrees in a number of lowness classes, in particular the classes of the degrees which lie below incomplete random degrees, indeed all LR-hard random degrees, and all ω-c.e. random degrees. The last result implies recent results of (...)
    Direct download (7 more)  
     
    Export citation  
     
    Bookmark   9 citations  
  • Complexity of Complexity and Strings with Maximal Plain and Prefix Kolmogorov Complexity.B. Bauwens & A. Shen - 2014 - Journal of Symbolic Logic 79 (2):620-632.
  • The Axiomatic Power of Kolmogorov Complexity.Laurent Bienvenu, Andrei Romashchenko, Alexander Shen, Antoine Taveneaux & Stijn Vermeeren - 2014 - Annals of Pure and Applied Logic 165 (9):1380-1402.
    The famous Gödel incompleteness theorem states that for every consistent, recursive, and sufficiently rich formal theory T there exist true statements that are unprovable in T . Such statements would be natural candidates for being added as axioms, but how can we obtain them? One classical approach is to add to some theory T an axiom that claims the consistency of T . In this paper we discuss another approach motivated by Chaitin's version of Gödel's theorem where axioms claiming the (...)
    Direct download (7 more)  
     
    Export citation  
     
    Bookmark