-1
$\begingroup$

Wikipedia claims that any halting probability (Chaitin's constant) is a normal number.

Since Chaitin's constant is uncomputble, how is a proof the the normalcy of the number possible? Computable numbers like pi and e are thought to be normal, yet there is no proof. It seems surprising to me that we have a proof of Chaitin's constant being normal although it is an uncomputable number, especially since "Chaitin's constant" isn't actually one number, but an infinite set of numbers (since it depends on the program encoding used).

Improve this question
$\endgroup$
7
  • 6
    $\begingroup$ See the answer to this question on mathoveflow: mathoverflow.net/questions/132099/… $\endgroup$
    – Marzio De Biasi
    Jul 22, 2014 at 15:50
  • 3
    $\begingroup$ As a high level intuition, Chaitin's constant is defined to be a random number (in the algorithmic randomness, i.e. Kolmogorov sense). Normality is one specific property of random numbers. $\endgroup$
    – Sasho Nikolov
    Jul 22, 2014 at 15:54
  • 2
    $\begingroup$ To add to my previous comment, the difficulty with proving that something like $\pi$ is normal is related to the fact that $\pi$ is computable. Because it is computable, it cannot have the strong randomness properties of Chaitin's constant. Then we need a more delicate argument to show that $\pi$ is just "random enough" to be normal. $\endgroup$
    – Sasho Nikolov
    Jul 22, 2014 at 19:13
  • 1
    $\begingroup$ @Sasho, those comments can be an answer. :) $\endgroup$
    – Kaveh
    Jul 22, 2014 at 23:44
  • 1
    $\begingroup$ @Kaveh I didn't feel confident enough in my expertise, but since no one has called me out on my comments, I will attempt an answer..a little later. $\endgroup$
    – Sasho Nikolov
    Jul 25, 2014 at 16:22

1 Answer 1

Reset to default
5
$\begingroup$

Marzio's comment gives a link to a formal proof that the Chaitin constant $\Omega$ is normal. Let me give some higher level intuition.

$\Omega$ is definened to be an algorithmically random number, in the Kolmogorov complexity sense. Check this beautiful answer by Laurent for a quick description of algorithmic randomness, or the wiki page. Or check the book by Li and Vitanyi. Normality is a specific property that random numbers have: intuitively, it is something you expect from a sequence of random digits, and when it fails that can be computably detected, so it must be a property of algorithmically random numbers. In other words, normality is a weak notion of randomness, while algorithmic randomness is a very strong one. It is easy to show that $\Omega$ is normal, because it satisfies the much stronger algorithmic randomness property, essentially by definition. On the other hand, it is hard to prove that computable constants like $\sqrt{2}$, $\pi$, and $e$ are normal, exactly because they are computable. No computable constant can be algorithmically random (because the algorithm that computes the constant can distinguish it from a random sequence), so to prove normality we need a much finer tool that shows that the constant is "random enough" to be normal, even though it is not algorithmically random. For the most part, we do not seem to have such fine tools yet.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.