Switch to: References

Add citations

You must login to add citations.
  1. 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 (...)
    Download  
     
    Export citation  
     
    Bookmark  
  • 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 (...)
    Download  
     
    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.
    Download  
     
    Export citation  
     
    Bookmark