Fundamenta Informaticae 56:273-284 (2003)

Toby Ord
Oxford University
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 No keywords specified (fix it)
Categories (categorize this paper)
Edit this record
Mark as duplicate
Export citation
Find it on Scholar
Request removal from index
Revision history

Download options

PhilArchive copy

Upload a copy of this paper     Check publisher's policy     Papers currently archived: 71,489
External links

Setup an account with your affiliations in order to access resources via your University's proxy server
Configure custom proxy (use this if your affiliation does not provide a proxy)
Through your library

References found in this work BETA

Hypercomputation: Computing More Than the Turing Machine.Toby Ord - 2002 - Dissertation, University of Melbourne

Add more references

Citations of this work BETA

Ω in Number Theory.Toby Ord - 2007 - In C. S. Calude (ed.), Randomness and Complexity, from Leibniz to Chaitin. World Scientific. pp. 161-173.

Add more citations

Similar books and articles


Added to PP index

Total views
37 ( #309,423 of 2,520,837 )

Recent downloads (6 months)
1 ( #405,623 of 2,520,837 )

How can I increase my downloads?


My notes