×

Several results in program size complexity. (English) Zbl 0459.68014


MSC:

68Q25 Analysis of algorithms and problem complexity
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Blum, M., On the size of machines, Information and Control, 11, 257-265 (1967) · Zbl 0165.02102
[2] Chaitin, G. J., On the length of programs for computing finite binary strings, J. ACM, 13, 322-337 (1966)
[3] Chaitin, G. J., A theory of program size formally identical to information theory, J. ACM, 22, 329-340 (1975) · Zbl 0309.68045
[4] Chaitin, G. J., Information theoretic characterizations of recursive infinite strings, Theoret. Comput. Sci., 2, 45-48 (1976) · Zbl 0328.02029
[5] Chaitin, G. J., Program size, oracles, and the jump operation, Osaka J. Math., 14, 139-149 (1977) · Zbl 0359.94031
[6] Daley, R. P., Complexity and randomness, (Computers Complexity Symposium, 7 (1973), Courant Institute: Courant Institute New York), 113-122
[7] Daley, R. P., Non-complex sequences: characterizations and examples, J. Symbolic Logic, 41, 626-638 (1976) · Zbl 0365.68054
[8] Gewirtz, W. L., Investigations in the theory of descriptive complexity, (Courant Computer Science Report 5 (1974), Courant Institute of Mathematical Sciences, New York University), 1-60
[9] Kamae, T., On Kolomogorov Complexity and information, Osaka J. Math., 10, 305-307 (1973) · Zbl 0273.94024
[10] Katseff, H. P., Complexity dips in infinite binary sequences, Information and Control, 38, 258-263 (1978) · Zbl 0399.94013
[11] Kolmogorov, A., Three Approaches for Defining the Concept of Information Quantity, (Selected Translations in Mathematical Statistics and Probability, 7 (1968), AMS Publications: AMS Publications Providence, RI)
[12] Knuth, D. E., The Art of Computer Programming, Vol. 1 (1968), Addison-Wesley: Addison-Wesley Reading · Zbl 0191.17903
[13] Loveland, D. W., A variant of the Kolmogorov concept of complexity, Information and Control, 15, 510-526 (1969) · Zbl 0188.52101
[14] Martin-Löf, P., Complexity oscillations in infinite binary sequences, Z. Wahrscheinlichkeitstheorie und Verw. Gebiete, 19 (1969)
[15] Rado, T., On Non-computable functions, Bell System Tech. J., 877-884 (1962) · Zbl 1497.68176
[16] Rogers, H., Gödel numberings of the partial recursive functions, J. Symbolic Logic, 23, 31-341 (1958)
[17] Rogers, H., Theory of Recursive Functions and Effective Computability (1968), McGraw-Hill: McGraw-Hill New York · Zbl 0183.01401
[18] Shoenfield, J. R., Degrees of Unsolvability (1971), American Elsevier: American Elsevier New York · Zbl 0119.25105
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.