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

Article type: Research Article

Authors: Ord, Toby | Kieu, Tien D.

Affiliations: Department of Philosophy, The University of Melbourne, Parkville 3010, Australia | Centre for Atom Optics and Ultrafast Spectroscopy, Swinburne University of Technology, Hawthorn 3122, Australia

Abstract: We show how to determine the k-th bit of Chaitin's algorithmically random real number Ω by solving k instances of the halting problem. From this we then reduce the problem of determining the k-th bit of Ω 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 Ω in number theory: an exponential Diophantine equation with a parameter k which has an odd number of solutions iff the k-th bit of Ω 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 Ω is 1.

Keywords: diophantine equation, Ω, algorithmic information theory, randomness, Hilbert's tenth problem

Journal: Fundamenta Informaticae, vol. 56, no. 3, pp. 273-284, 2003