×

Information-theoretic characterizations of recursive infinite strings. (English) Zbl 0328.02029


MSC:

03D80 Applications of computability and recursion theory
68Q25 Analysis of algorithms and problem complexity
94A15 Information theory (general)
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Chaitin, G. J., Information-theoretic aspects of the Turing degrees, Abstract 72T-E77. Abstract 72T-E77, AMS Notices, 19 (1972), A-602 · Zbl 0782.68005
[2] Chaitin, G. J., There are few minimal descriptions. A necessary and sufficient condition for an infinite binary string to be recursive, Recursive Function Theory Newsletter, 13-14 (January 1973), (Abstract)
[3] Chaitin, G. J., A theory of program size formally identical to information theory, J. ACM, 22, 329-340 (1975) · Zbl 0309.68045
[4] Loveland, D. W., A variant of the Kolmogorov concept of complexity, Information and Control, 15, 510-526 (1969) · Zbl 0188.52101
[5] Schnorr, C. P., Process complexity and effective random tests, J. Comput. System Sci., 7, 376-388 (1973) · Zbl 0273.68036
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.