An Algebraic Characterization of the Halting Probability

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

Abstrakty

EN

Using 1947 work of Post showing that the word problem for semigroups is unsolvable, we explicitly exhibit an algebraic characterization of the bits of the halting probability W. Our proof closely follows a 1978 formulation of Post's work by M. Davis. The proof is self-contained and not very complicated.

Słowa kluczowe

EN

halting probability; word problem

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2007
• Tom: Vol. 79, nr 1-2
• Strony: 17--23
• Opis fizyczny: bibliogr. 10 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] M. Davis, "What is a computation?", in L. A. Steen,Mathematics Today: Twelve Informal Essays, Springer-Verlag, New York, 1978, pp. 241-267. Reprinted in Calude [8].
• [2] E. Post, "Recursive unsolvability of a problem of Thue," Journal of Symbolic Logic, Vol. 12 (1947), pp. 1-11. Reprinted in Davis [3, pp. 293-303].
• [3] M. Davis, The Undecidable, Dover, 2004.
• [4] G. Chaitin, Algorithmic Information Theory, Cambridge University Press, 1987.
• [5] T. Ord, T. D. Kieu, "On the existence of a new family of diophantine equations for ," Fundamenta Informaticae, Vol. 56 (2003), pp. 273-284.
• [6] G. Chaitin, Meta Math!, Pantheon, 2005.
• [7] G. Chaitin, The Limits of Mathematics, Springer-Verlag, 1998.
• [8] C. Calude, Randomness & Complexity, from Leibniz to Chaitin, World Scientific, to appear.
• [9] J. J. Rotman, An Introduction to the Theory of Groups, Fourth edition, Springer-Verlag, 1995, Corrected second printing, 1999.
• [10] G. Chaitin, Thinking about Gödel & Turing: Essays on Complexity, 1970-2007, in preparation.