The Halting Probability via Wang Tiles

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

Abstrakty

EN

Using work of Hao Wang, we exhibit a tiling characterization of the bits of the halting probability.

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2008
• Tom: Vol. 86, nr 4
• Strony: 429--433
• Opis fizyczny: bibliogr.7 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] B. Grünbaum, G. C. Shephard, Tilings and Patterns, W. H. Freeman, 1987, Chapter 11.
• [2] G. Chaitin, Algorithmic Information Theory, Cambridge University Press, 1987.
• [3] T. Ord, T. D. Kieu, "On the existence of a new family of diophantine equations for ," Fundamenta Informaticae, Vol. 56 (2003), pp. 273-284.
• [4] G. Chaitin, "An algebraic characterization of the halting probability," Fundamenta Informaticae, Vol. 79 (2007), pp. 17-23.
• [5] G. Chaitin, Meta Math!, Pantheon, 2005.
• [6] G. Chaitin, The Limits of Mathematics, Springer-Verlag, 1998.
• [7] G. Chaitin, Thinking about Gödel & Turing: Essays on Complexity, 1970-2007, World Scientific, 2007.