Probability and Program-Size for Functions

• Autorzy: Chaitin G.
• Języki publikacji: EN

Abstrakty

EN

We show that unlike the general case of the relationship between algorithmic probability and program-size for enumerating sets, in the case of the graphs of total functions these two quantities are closely related.

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2006
• Tom: Vol. 71, nr 4
• Strony: 367--370
• Opis fizyczny: bibliogr. 6 poz.

Twórcy

autor

Chaitin G.

• IBM T.J. Watson Research Center P.O. Box 218, Yorktown Heights NY 10598, U.S.A.,

Bibliografia

• [1] Chaitin, G. J., "A theory of program size formally identical to information theory," Journal of the ACM 22 (1975), pp. 329-340.
• [2] Chaitin, G. J., Exploring Randomness, Springer-Verlag, 2001.
• [3] Calude, C. S., Information and Randomness, Springer-Verlag, 2002.
• [4] Downey, R. and D. Hirschfeldt, Algorithmic Randomness and Complexity, in preparation.
• [5] Chaitin, G. J., "Algorithmic entropy of sets," Computers & Mathematics with Applications 2 (1976), pp. 233-245.
• [6] Solovay, R. M., "On random r.e. sets," in A. I. Arruda, N. C. A. da Costa, and R. Chuaqui, Non-Classical Logics, Model Theory, and Computability, North-Holland, Amsterdam, 1977, pp. 283-307.