Schmidhuber, Jürgen Hierarchies of generalized Kolmogorov complexities and nonenumerable universal measures computable in the limit. (English) Zbl 1066.68058 Int. J. Found. Comput. Sci. 13, No. 4, 587-612 (2002). 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. Cited in 12 Documents MSC: 68Q30 Algorithmic information theory (Kolmogorov complexity, etc.) 03D10 Turing machines and related notions 03D30 Other degrees and reducibilities in computability and recursion theory Keywords:computability in the limit; generalized algorithmic probability; generalized Kolmogorov complexity hierarchy; halting probability Omega; cumulatively enumerable measures; computable universes PDFBibTeX XMLCite \textit{J. Schmidhuber}, Int. J. Found. Comput. Sci. 13, No. 4, 587--612 (2002; Zbl 1066.68058) 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.