✦ LIBER ✦
Kolmogorov complexity and characteristic constants of formal theories of arithmetic
✍ Scribed by Shingo Ibuka; Makoto Kikuchi; Hirotaka Kikyo
- Publisher
- John Wiley and Sons
- Year
- 2011
- Tongue
- English
- Weight
- 84 KB
- Volume
- 57
- Category
- Article
- ISSN
- 0044-3050
No coin nor oath required. For personal study only.
✦ Synopsis
We investigate two constants c T and r T , introduced by Chaitin and Raatikainen respectively, defined for each recursively axiomatizable consistent theory T and universal Turing machine used to determine Kolmogorov complexity. Raatikainen argued that c T does not represent the complexity of T and found that for two theories S and T, one can always find a universal Turing machine such that c S = c T . We prove the following are equivalent: c S = c T for some universal Turing machine, r S = r T for some universal Turing machine, and T proves some Π1 -sentence which S cannnot prove.