Name
Abstract | ||
|---|---|---|
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) not equal c(T) for some universal Turing machine, r(S) not equal r(T) for some universal Turing machine, and T proves some Pi(1)-sentence which S cannnot prove. (C) 2011 WILEY-VCH Verlag GmbH & Co. KGaA, Weinheim |
Year | DOI | Venue |
|---|---|---|
2011 | 10.1002/malq.201010017 | MATHEMATICAL LOGIC QUARTERLY |
Keywords | Field | DocType |
Characteristic constant,Kolmogorov complexity | 2-EXPTIME,Discrete mathematics,Universal Turing machine,Kolmogorov complexity,PSPACE,Turing reduction,Description number,Alternating Turing machine,Time hierarchy theorem,Mathematics | Journal |
Volume | Issue | ISSN |
57 | 5 | 0942-5616 |
Citations | PageRank | References |
0 | 0.34 | 2 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Shingo Ibuka | 1 | 0 | 0.68 |
| Makoto Kikuchi | 2 | 0 | 0.34 |
| Hirotaka Kikyo | 3 | 16 | 5.26 |