×

zbMATH — the first resource for mathematics

Information, randomness and incompleteness. Papers on algorithmic information theory. (English) Zbl 1013.00525
Series in Computer Science. 8. Singapore: World Scientific. x, 272 p. (1987).
Contents: “Randomness and mathematical proof” [Sci. Am. 232, 47-52 (1975)] (pp. 3-13); “On the difficulty of computations” [IEEE Trans. Inf. Theory 16, 5-9 (1970; Zbl 0184.20501)] (pp. 14-22); “Information-theoretic computational complexity” [ibid. 20, 10-15 (1974; Zbl 0282.68022)] (pp. 23-32); “Algorithmic information theory” [in: Encyclopedia of statistical sciences, Vol. 1, 38-41, Wiley, New York (1982; Zbl 0552.62001)] (pp. 33-37); “Algorithmic information theory” [IBM J. Res. Develop. 21, 350-359 (1977; Zbl 0362.94035)] (pp. 38-52); “Gödel’s theorem and information” [Int. J. Theor. Phys. 21, 941-954 (1982)](pp. 55-65); “Randomness and Gödel’s theorem” (pp. 66-69); “An algebraic equation for the halting probability” [The universal Turing machine, a half-century survey, 279-283 (1988; Zbl 0661.03032)] (pp. 70-73); “Computing the busy beaver function” [in: Open problems in communication and computation. Springer, Berlin, 108-112 (1988; Zbl 0628.68001)] (pp. 74-76); “To a mathematical definition of ‘life”’ [ACM SICACT News 4, 12-18 (1970)] (pp. 79-85); “Toward a mathematical definition of ‘life”’ [in: The maximum entropy formalism. Cambridge, MA, 1978, MIT Press, Cambridge, MA, 477-498 (1979; Zbl 0467.94001)] (pp. 86-104); “A theory of program size formally identical to information theory” [J. Assoc. Comput. Mach. 22, 329-340 (1975; Zbl 0309.68045)] (pp. 107-122); “Incompleteness theorems for random reals” [Adv. Appl. Math. 8, 119-146 (1987; Zbl 0649.03046)] (pp. 123-146); “Algorithmic entropy of sets” [Comput. Math. Appl. 2, 233-245 (1976; Zbl 0367.68036)] (pp. 147-162); “Information-theoretic limitations of formal systems” [J. Assoc. Comput. Mach. 21, 403-424 (1974; Zbl 0287.68027)] (pp. 165-190); (with Jacob T. Schwartz) “A note on Monte Carlo primality tests and algorithmic information theory” [Commun. Pure Appl. Math. 31, 521-527 (1978; Zbl 0401.94008)] (pp. 191-196); “Information-theoretic characterizations of recursive infinite strings” [Theor. Comput. Sci. 2, 45-48 (1976; Zbl 0328.02029)] (pp. 197-200); “Program size, oracles, and the jump operation” [Osaka J. Math. 14, 139-149 (1977; Zbl 0359.94031)] (pp. 201-209); “On the length of programs for computing finite binary sequences” [J. Assoc. Comput. Mach. 13, 547-569 (1966; Zbl 0158.25301)] (pp. 213-238); “On the length of programs for computing finite binary sequences: statistical considerations” [ibid. 16, 145-159 (1969; Zbl 0187.28303)] (pp. 239-255); “On the simplicity and speed of programs for computing infinite sets of natural numbers” [ibid. 16, 407-422 (1969; Zbl 0187.28401)] (pp. 256-272).

MSC:
00B60 Collections of reprinted articles
01A75 Collected or selected works; reprintings or translations of classics
03D20 Recursive functions and relations, subrecursive hierarchies
68Q30 Algorithmic information theory (Kolmogorov complexity, etc.)
94A15 Information theory (general)
PDF BibTeX Cite