Very Simple Chaitin Machines for Concrete AIT

• Autorzy: Stay M.
• Języki publikacji: EN

Abstrakty

EN

In 1975, Chaitin introduced his celebrated Omega number, the halting probability of a universal Chaitin machine, a universal Turing machine with a prefix-free domain. The Omega number's bits are algorithmically random-there is no reason the bits should be the way they are, if we define "reason" to be a computable explanation smaller than the data itself. Since that time, only two explicit universal Chaitin machines have been proposed, both by Chaitin himself. Concrete algorithmic information theory involves the study of particular universal Turing machines, about which one can state theorems with specific numerical bounds, rather than include terms like O(1). We present several new tiny Chaitin machines (those with a prefix-free domain) suitable for the study of concrete algorithmic information theory. One of the machines, which we call Keraia, is a binary encoding of lambda calculus based on a curried lambda operator. Source code is included in the appendices. We also give an algorithm for restricting the domain of blank-endmarker machines to a prefix-free domain over an alphabet that does not include the endmarker; this allows one to take many universal Turing machines and construct universal Chaitin machines from them.

Słowa kluczowe

EN

Chaitin machine; lambda calculus

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2005
• Tom: Vol. 68, nr 3
• Strony: 231--247
• Opis fizyczny: Bibliogr. 20 poz.

Twórcy

autor

Stay M.

• Department of Computer Science The University of Auckland Private Bag 920/9, Auckland, New Zealand,

Bibliografia

• [1] Barker, C. “Iota and Jot: the simplest languages?” 2001.htp://ling.ucsd.edu/~barker/Iota.
• [2] Barker, C. “Zot.” 2002. htp://ling.ucsd.edu/~barker/Iota/zot.htlm.
• [3] Calude, C. S. Information and Randomness - An Algorithmic Perspective. 2nd Edition, Revised and Extended, Springer-Verlag, Berlin, 2002. p. 24, 104
• [4] Calude, C., Dinneen, M. J., and Shu, C.-K. “Computing a glimpse of randomness,” Experimental Mathematics, 2 (2002), 369-378
• [5] Chaitin, G. J. “On the lengths of programs for computing binary sequences.” J. Assoc. Comput. Mach. 13, 549-569. 1966.
• [6] Chaitin, G. J. “A theory of program size formally identical to information theory,” Journal of the ACM 22 (1975), pp. 329-340. http://www.cs.auckland.ac.nz./CDMTCS/chaitin/acm75.pdf.
• _[7] Chaitin, G. J. “algorithmic information theory.” IBM Journal of Research and Development 21 (1977), pp. 350-359, 496.
• [8] Chaitin, G. J. algorithmic Information Theory. Cambridge University Press, Cambridge, 1987. http://www.cs.auckland.ac.nz./CDMTCS/chaitin/cup.html.
• [9] Chaitin, G. J. “An Invitation to algorithmic Information Theory,” DMTCS’96 Proceedings, Springer Verlag, Singapore, 1997, pp. 1-23. http://www.cs.auckland.ac.nz./CDMTCS/chaitin/inv.htlm.
• [10] Chaitin, G. J. “Elegant Lisp Programs,” People and Ideas in Theoretical Computer Science, C. Calude, ed. Springer-Verlag Singapore, 1999, pp. 32-52. http://www.cs.auckland.ac.nz./CDMTCS/chaitin/li[s.htlm.
• [11] Church, A. “An unsolvable problem of elementary number theory,” American Journal of Mathematics, 58 (1936), pp. 345-363.
• [12] Church, A. “A note on the Entscheidungsproblem,” Journal of Symbolic Logic, 1 (1936), pp. 40-41.
• [13] de Bruijn, N. G. “Lambda calculus notation with nameless dummies, a tool for automatic formula manipulation,”Indagationes Mathematicae 34, 381-392, 1972.
• [14] Fokker, J. “The systematic construction of a one-combinator basis for Lambda-terms,” Formal Aspects of Computing 4:776-780. 1992. http://www.cs.uu.nl/people/jeroen/article/combinat/combinat.ps.
• [15] Kolmogorov, A. N. “Three approaches to the quantitative definition of information.” Prob. Inform. Transmission. 1, pp. 4-7. 1965.
• [16] Rudiak-Gould, B. “Lazy-K.” http://homepages.ci.nl/~tromp/cl/lazy-k.html.
• [17] Shannon, C. E. “A mathematical theory of communication,” Bell System Technical Journal, vol. 27, pp. 379-423 and 623-656, July and October, 1948. http://cm.bell-labs.com/cm/ms/what/shannonday/paper.html.
• [18] Solomonoff, R. J. “A formal theory of inductive inferrence I, II.” Inform. Control 7, 1-22, 224-254. 1964.
• [19] Tromp, J. “Binary Lambda Calculus and Combinatory Logic.” Sep 14, 2004. http://homepages.ci.nl/~tromp/cl/LC.pdf.
• [20] Turing, A. “On computable numbers, with an application to the Entscheidungsproblem,”Proceedings of the London Mathematical Society, Series 2, 42 (1936), pp 230-265. Errata appeared in Series 2, 43 (1937), pp 544-546.