zbMATH — the first resource for mathematics

There in no sw-complete c.e. real. (English) Zbl 1070.03028
A real number \(\alpha\) is called random if for every \(n\), the sequence \(\alpha_{| n}\) of its first \(n\) binary digits cannot be compressed, i.e., if \(K(\alpha_{| n})\geq n-O(1)\), where \(K(z)\) is a prefix-free Kolmogorov complexity of the sequence \(z\) (i.e., crudely speaking, the shortest length of a program that computes a binary sequence starting with \(z\)).
For computably enumerable (c.e.) real numbers, we can define when one of them is “more random” than another: \(\alpha\leq _K \beta\) if and only if \(K(\alpha_{| n})\leq K(\beta_{| n})+O(1)\). It is known that Chaitin’s \(\Omega\) (the halting probability of a universal prefix-free Turing machine) is random and c.e. and it is “more random” than any other c.e. real \(\beta\) in the sense that \(\beta\leq _K \Omega\).
It is difficult to compute Kolmogorov complexity, so a new definition of sw-reducibility (strongly weak truth table reducibility) \(\leq_{\text{sw}}\) was proposed. It is known that sw-reducibility implies \(\beta \leq_K\alpha\). Because of this, it was conjectured that there exists an sw-complete c.e. real number, i.e., a c.e. real number \(\alpha\) such that \(\beta \leq_{\text{sw}}\alpha\) for all c.e. real numbers \(\beta\). The authors prove that there is no such number; moreover, they prove that there exist two non-random c.e. reals \(\beta_0\) and \(\beta_1\) for which no c.e. real \(\alpha\) exists for which \(\beta_0\leq_{\text{sw}}\alpha\) and \(\beta_1\leq _{\text{sw}}\alpha\).

03D80 Applications of computability and recursion theory
68Q30 Algorithmic information theory (Kolmogorov complexity, etc.)
Full Text: DOI
[1] Advances in Applied Mathematics 8 pp 119–146– (1987)
[2] Algorithmic information theory (1987)
[3] Journal of the Association for Computing Machinery 13 pp 547–569– (1966)
[4] Stacs ’98 1373 pp 596–606– (1998)
[5] Information and Control 7 pp 224–254– (1964)
[6] Recursively enumerable sets and degrees (1987)
[7] Transactions of the American Mathematical Society 140 pp 271–294– (1969)
[8] An introduction to Kolmogorov complexity and its applications (1997) · Zbl 0866.68051
[9] Information and Control 9 pp 602–619– (1966)
[10] Randomness and recursive enumerability, SIAM Journal on Computing 31 pp 199–211– (2001)
[11] Problems of Information Transmission (Problemy Peredachi Informatsü) 1 pp 1–7– (1965)
[12] Journal of Computer and System Sciences 68 pp 96–114– (2004)
[13] Algorithmic randomness and complexity · Zbl 0815.60003
[14] Zufälligkeit und Wahrscheinlichkeit 218 (1971)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.