The axiomatic power of Kolmogorov complexity
From MaRDI portal
Publication:2453066
Abstract: The famous G"odel incompleteness theorem states that for every consistent 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 (and well studied) 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"odel's theorem where axioms claiming the randomness (or incompressibility) of some strings are probabilistically added, and show that it is not really useful, in the sense that this does not help us to prove new interesting theorems. This result answers a question recently asked by Lipton. The situation changes if we take into account the size of the proofs: randomly chosen axioms may help making proofs much shorter, unless NP=PSPACE. We then study the axiomatic power of the statements of type "the Kolmogorov complexity of x exceeds n" in general. They are Pi_1 (universally quantified) statements of Peano arithmetic. We show that by adding all true statements of this type, we obtain a theory that proves all true Pi_1-statements, and also provide a more detailed classification. In particular, to derive all true Pi_1-statements it is sufficient to add one statement of this type for each n (or even for infinitely many n) if strings are chosen in a special way. On the other hand, one may add statements of this type for most x of length n (for every n) and still obtain a weak theory. We also study other logical questions related to "random axioms". Finally, we consider a theory that claims Martin-L"of randomness of a given infinite binary sequence. This claim can be formalized in different ways. We show that different formalizations are closely related but not equivalent, and study their properties.
Recommendations
Cites work
- Algorithmic randomness and complexity.
- Algorithmic tests and randomness with respect to a class of measures
- An introduction to Kolmogorov complexity and its applications
- Computability and randomness
- Enumerations of the Kolmogorov function
- Evaluating the complexity of mathematical problems. I
- scientific article; zbMATH DE number 5595151 (Why is no real title available?)
- scientific article; zbMATH DE number 4135927 (Why is no real title available?)
- scientific article; zbMATH DE number 5772857 (Why is no real title available?)
- Incompleteness theorems for random reals
- Propagation of partial randomness
- RELATIVIZING CHAITIN'S HALTING PROBABILITY
- ∏ 0 1 Classes and Degrees of Theories
Cited in
(10)- Kolmogorov complexity and the second incompleteness theorem
- An additivity theorem for plain Kolmogorov complexity
- Axiomatizing Kolmogorov complexity
- Revisiting Chaitin's incompleteness theorem
- A note on the Kolmogorov data complexity and nonuniform logical definitions
- Towards an axiomatic system for Kolmogorov complexity
- Kolmogorov complexity and characteristic constants of formal theories of arithmetic
- scientific article; zbMATH DE number 1236369 (Why is no real title available?)
- scientific article; zbMATH DE number 7139948 (Why is no real title available?)
- Approximating Kolmogorov complexity
This page was built for publication: The axiomatic power of Kolmogorov complexity
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2453066)
