×

Hierarchies of generalized Kolmogorov complexities and nonenumerable universal measures computable in the limit. (English) Zbl 1066.68058

Summary: The traditional theory of Kolmogorov complexity and algorithmic probability focuses on monotone Turing machines with one-way write-only output tape. This naturally leads to the universal enumerable Solomonoff-Levin measure. Here we introduce more general, nonenumerable but cumulatively enumerable measures (CEMs) derived from Turing machines with lexicographically nondecreasing output and random input, and even more general approximable measures and distributions computable in the limit. We obtain a natural hierarchy of generalizations of algorithmic probability and Kolmogorov complexity, suggesting that the “true” information content of some (possibly infinite) bitstring \(x\) is the size of the shortest nonhalting program that converges to \(x\) and nothing but \(x\) on a Turing machine that can edit its previous outputs. Among other things we show that there are objects computable in the limit yet more random than Chaitin’s “number of wisdom” Omega, that any approximable measure of \(x\) is small for any \(x\) lacking a short description, that there is no universal approximable distribution, that there is a universal CEM, and that any nonenumerable CEM of \(x\) is small for any \(x\) lacking a short enumerating program. We briefly mention consequences for universes sampled from such priors.

MSC:

68Q30 Algorithmic information theory (Kolmogorov complexity, etc.)
03D10 Turing machines and related notions
03D30 Other degrees and reducibilities in computability and recursion theory
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] DOI: 10.1038/35005001 · Zbl 1369.81023 · doi:10.1038/35005001
[2] DOI: 10.1016/0020-0190(87)90114-1 · Zbl 0653.68084 · doi:10.1016/0020-0190(87)90114-1
[3] Cantor G., Crelle’s Journal fur Mathematik 77 pp 258– (1874)
[4] DOI: 10.1145/321495.321506 · Zbl 0187.28303 · doi:10.1145/321495.321506
[5] Freyvald R. V., Transactions of Latvijas Vlasts Univ. Zinatn. Raksti 210 pp 6– (1977)
[6] Gacs P., Soviet Math. Dokl. 15 pp 1477– (1974)
[7] DOI: 10.1016/0304-3975(83)90139-1 · Zbl 0562.68035 · doi:10.1016/0304-3975(83)90139-1
[8] DOI: 10.1007/BF01700692 · Zbl 0002.00101 · doi:10.1007/BF01700692
[9] DOI: 10.2307/2270580 · Zbl 0203.01201 · doi:10.2307/2270580
[10] Gregorczyk A., Fundamenta Mathematicae 44 pp 61– (1957)
[11] DOI: 10.1109/JRPROC.1952.273898 · Zbl 0137.13605 · doi:10.1109/JRPROC.1952.273898
[12] Hutter M., Switzerland pp 0101019– (2001)
[13] DOI: 10.1006/jcss.2000.1743 · Zbl 0983.68083 · doi:10.1006/jcss.2000.1743
[14] Kolmogorov A.N., Problems of Information Transmission 1 pp 1– (1965) · Zbl 0271.94018
[15] DOI: 10.1016/0168-0072(93)90209-V · Zbl 0788.68068 · doi:10.1016/0168-0072(93)90209-V
[16] Levin L. A., Soviet Math. Dokl. 14 (5) pp 1413– (1973)
[17] Levin L. A., Problems of Information Transmission 10 (3) pp 206– (1974)
[18] DOI: 10.1016/S0019-9958(66)80018-9 · Zbl 0244.62008 · doi:10.1016/S0019-9958(66)80018-9
[19] Mostowski A., Fundamenta Mathematicae 44 pp 37– (1957)
[20] DOI: 10.2307/2270581 · Zbl 0193.30102 · doi:10.2307/2270581
[21] DOI: 10.1016/S0022-0000(73)80030-3 · Zbl 0273.68036 · doi:10.1016/S0022-0000(73)80030-3
[22] DOI: 10.1002/j.1538-7305.1948.tb01338.x · Zbl 1154.94303 · doi:10.1002/j.1538-7305.1948.tb01338.x
[23] DOI: 10.1016/S0019-9958(64)90223-2 · Zbl 0258.68045 · doi:10.1016/S0019-9958(64)90223-2
[24] DOI: 10.1109/TIT.1978.1055913 · Zbl 0382.60003 · doi:10.1109/TIT.1978.1055913
[25] Turing A. M., Proceedings of the London Mathematical Society, Series 2 pp 230– (1936)
[26] DOI: 10.1016/S0304-3975(98)00073-5 · Zbl 0915.68079 · doi:10.1016/S0304-3975(98)00073-5
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.