Name
Abstract | ||
|---|---|---|
Chaitin discovered that for each formal system T, there exists a constant csuch that no sentence of the form K(x) cis provable in T, where K(x) is the Kolmogorov complexity of x. We call the minimum such cthe Chaitin characteristic constant of T, or cT. There have been discussions about whether it represents the information content or strength of T. Raatikainen tried to reveal the true source of cT, stating that it is determined by the smallest index of Turing machine which does not halt but we cannot prove this fact in T. We call the index the Raatikainen characteristic constant of T, denoted by rT. We show that rTdoes not necessarily coincide with cT; for two arithmetical theories T, T茂戮驴with a 茂戮驴1-sentence provable in T茂戮驴but not in T, there is an enumeration of the Turing machines such that rTrT茂戮驴and cT= cT茂戮驴. |
Year | DOI | Venue |
|---|---|---|
2008 | 10.1007/978-3-540-69937-8_19 | WoLLIC |
Keywords | Field | DocType |
kolmogorov complexity,turing machine,form k,smallest index,1-sentence provable,cthe chaitin,t. raatikainen,arithmetical theory,cis provable,constant csuch,characteristic constants,indexation,information content | Discrete mathematics,Formal system,Arithmetic function,Kolmogorov complexity,Of the form,Existential quantification,Enumeration,Algorithm,Turing machine,Sentence,Mathematics | Conference |
Volume | ISSN | Citations |
5110 | 0302-9743 | 0 |
PageRank | References | Authors |
0.34 | 3 | 3 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Shingo Ibuka | 1 | 0 | 0.68 |
| Makoto Kikuchi | 2 | 3 | 2.16 |
| Hirotaka Kikyo | 3 | 16 | 5.26 |