On the existence of a new family of Diophantine equations for Omega

• Autorzy: Ord T. , Kieu T.D.
• Języki publikacji: EN

Abstrakty

EN

We show how to determine the k-th bit of Chaitin's algorithmically random real number W by solving k instances of the halting problem. From this we then reduce the problem of determining the k-th bit of W to determining whether a certain Diophantine equation with two parameters, k and N, has solutions for an odd or an even number of values of N. We also demonstrate two further examples of W in number theory: an exponential Diophantine equation with a parameter k which has an odd number of solutions iff the k-th bit of W is 1, and a polynomial of positive integer variables and a parameter k that takes on an odd number of positive values iff the k-th bit of W is 1.

Słowa kluczowe

EN

diophantine equations; algorithmic Information theory; randomness; Hilbert's tenth problem

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2003
• Tom: Vol. 56, nr 3
• Strony: 273--284
• Opis fizyczny: bibliogr. 10 poz.

Twórcy

autor

Ord T.

autor

Kieu T.D.

• Centre for Atom Optics and Ultrafast Spectroscopy, Swinburne University of technology, Hawthorn 3122, Australia,

Bibliografia

• [1] Calude, C. S.: A Characterization of c.e. Random Reals, Theoretical Computer Science, 271, 2002, 3-14.
• [2] Calude, C. S., Nies, A.: Chaitin Numbers and Strong Reducibilities, Journal of Universal Computer Science, 3, 1997, 1162-1166.
• [3] Chaitin, G. J.: A Theory of Program Size Formally Identical to Information Theory, Journal of the ACM, 22(3), July 1975, 329-340.
• [4] Chaitin, G. J.: Algorithmic Information Theory, Cambridge University Press, Cambridge, 1987.
• [5] Copeland, B. J.: Hypercomputation, Minds and Machines, 12, 2002, 461-502.
• [6] Copeland, B. J., Proudfoot, D.: Alan Turing’s Forgotten Ideas in Computer Science, Scientific American, April 1999, 77-81.
• [7] Kieu, T. D.: Computing the Noncomputable, Contemporary Physics, 44, 2003, 51-71.
• [8] Matiyasevich, Y. V.: Hilbert’s Tenth Problem, MIT Press, Cambridge, Massachusetts, 1993.
• [9] Ord, T.: Hypercomputation: Computing More Than the Turing Machine, Technical report, University of Melbourne, Melbourne, Australia, September 2002, Available at http://www.arxiv.org/abs/math.LO/0209332.
• [10] Solovay, R. M.: A Version of for which ZFC Can Not Predict a Single Bit, in: Finite Versus Infinite. Contributions to an Eternal Dilemma (C. S. Calude, G. P˘aun, Eds.), Springer, London, 2000, 323-334.