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

<p>$\Omega$ is definened to be an algorithmically random number, in the Kolmogorov complexity sense. Check this beautiful <a href="https://cstheory.stackexchange.com/a/1415/4896">answer</a> by Laurent for a quick description of algorithmic randomness, or the <a href="http://en.wikipedia.org/wiki/Algorithmically_random_sequence" rel="nofollow noreferrer">wiki page</a>. Or check the <a href="http://books.google.com/books?id=25fue3UYDN0C&amp;lpg=PR1&amp;dq=kolmogorov%20complexity&amp;pg=PA220#v=onepage&amp;q&amp;f=false" rel="nofollow noreferrer">book by Li and Vitanyi</a>. 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, <strong>exactly because</strong> 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. </p>

CC BY-SA 3.0
2014-07-25T17:34:55.010Z
2014-07-25T20:12:13.290Z
2017-04-13T12:32:28.167Z
Sasho Nikolov
<p><a href="http://en.wikipedia.org/wiki/Chaitin%27s_constant" rel="nofollow">Wikipedia</a> claims that any halting probability (Chaitin's constant) is a normal number.</p>

<p>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). </p>

CC BY-SA 3.0
2014-07-22T15:50:08.960Z
See the answer to this question on mathoveflow: http://mathoverflow.net/questions/132099/normality-of-chaitins-constant
Marzio De Biasi
CC BY-SA 3.0
2014-07-22T15:54:16.190Z
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.
Sasho Nikolov
CC BY-SA 3.0
2014-07-22T19:13:44.853Z
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.
Sasho Nikolov
CC BY-SA 3.0
2014-07-22T23:44:56.593Z
@Sasho, those comments can be an answer. :)
Kaveh
CC BY-SA 3.0
2014-07-25T16:22:47.577Z
@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.
Sasho Nikolov
CC BY-SA 3.0
2014-07-25T22:51:49.140Z
If the answer is on Wikipedia, the proof that the answer is correct probably isn't a research-level question.
David Richerby
CC BY-SA 3.0
2014-07-27T18:50:47.280Z
@DavidRicherby For what it's worth, the MO question asking for a proof has +7 votes, and MO is a research-level site. Your wiki heuristic seems suspect too: the P vs NP wiki page mentions algebrization, but I'd say a question about it has every possibility to be research level. That said, the current question does seem a bit basic.
Sasho Nikolov
<computability><it.information-theory>
How can you prove that all halting probabilites are normal real numbers?
Nathan BeDell
# How can you prove that all halting probabilites are normal real numbers?

(Asked by: username_0 on 2014-07-22)

[Wikipedia](http://en.wikipedia.org/wiki/Chaitin%27s_constant) 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).

**Tags:** computability, it.information-theory

> **Comments:**
> **username_1**: See the answer to this question on mathoveflow: http://mathoverflow.net/questions/132099/normality-of-chaitins-constant  
> **username_2**: 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.  
> **username_2**: 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.  
> **username_3**: @Sasho, those comments can be an answer. :)  
> **username_2**: @username_3 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.  
> **username_4**: If the answer is on Wikipedia, the proof that the answer is correct probably isn't a research-level question.  
> **username_2**: @DavidRicherby For what it's worth, the MO question asking for a proof has +7 votes, and MO is a research-level site. Your wiki heuristic seems suspect too: the P vs NP wiki page mentions algebrization, but I'd say a question about it has every possibility to be research level. That said, the current question does seem a bit basic.  

---

## 1 answers

### Answer by username_2 on 2014-07-25. Score: 5

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](https://cstheory.stackexchange.com/a/1415/4896) by Laurent for a quick description of algorithmic randomness, or the [wiki page](http://en.wikipedia.org/wiki/Algorithmically_random_sequence). Or check the [book by Li and Vitanyi](http://books.google.com/books?id=25fue3UYDN0C&lpg=PR1&dq=kolmogorov%20complexity&pg=PA220#v=onepage&q&f=false). 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.


---

