What is known about irrationality measure of the Chaitin's constant $\Omega$? Is it finite? Can it be a computable number? Can it be $2$?
Irrationality measure of the Chaitin's constant $\Omega$
-
0The Wikipedia article you link to has an entire section on the uncomputability of halting probabilities. It also explains that the halting probability depends on the program encoding used, so different halting probabilities might have different irrationality measures. Since they're uncomputable, they're transcendental, so their irrationality measure is at least $2$. – 2011-12-13
-
0Have you made any progress on this question? I like it and think it deserves more attention. – 2012-01-14
-
0@joriki It would be interesting though, if the irrationality measure was independent of the machine used. – 2012-01-14
-
0@QuinnCulver Unfortunately, I still do not know the answer. – 2012-01-15
-
0@VladimirReshetnikov Why not offer a bounty then? – 2012-01-16
1 Answers
Since $\Omega$ is incompressible, its irrationality measure must be 2. In more detail:
If the irrationality measure of $\Omega$ were some $\alpha>2$, pick any $\beta$ in $(2,\alpha)$. Then there would be infinitely many pairs $(p,q)$ of integers $p$ and $q>0$ with $|p/q-\Omega| Given such a pair with $q\ge 2$, let $n:=\lfloor{\beta \log_2 q-1}\rfloor$. Given the triple $(n,p,q)$, we can then determine that the first $n$ bits of $\Omega$ are given by $$\lfloor{2^n \Omega}\rfloor=\lfloor{\delta+(2^np/q)}\rfloor,\qquad\delta\in[-\frac{1}{2},\frac12]. \qquad(*)$$ Letting $m:=\lfloor{(2^np/q)-\frac{1}{2}}\rfloor$, we can see that the right-hand side of (*) varies over exactly the values $m$ and $m+1$ as $\delta$ runs over $[-\frac12,\frac12]$. Therefore, (*) must hold for either $\delta=-1/2$ or $\delta=1/2$, so the first $n$ bits of $\Omega$ can be computed from the quadruple $(n,p,q,\delta)$, $\delta\in\{\pm \frac12\}.$ Let $K(x)$ be the prefix Kolmogorov complexity of a string $x$ (see e.g. $\S 3.1$, [Li and Vitányi 2008] for this definition.) Then there is some constant $c>0$ such that, for all $n$, if $\Omega[1:n]$ is the first $n$ bits of $\Omega$, then $$K(\Omega[1:n])\ge n-c \qquad\hbox{(Lemma 3.6.2, [Li and Vitányi 2008].) }\qquad(**)$$ But, using a prefix code, we can code the quadruple $(n,p,q,\delta)$ in no more than $2\log_2 q+O(\log \log q)=\frac{2}{\beta}n+O(\log n)$ bits. Therefore, for infinitely many $n$, $$ K(\Omega[1:n])\le\frac{2}{\beta}n+O(\log n), $$ contradicting (**).
-
0It seems you need for there to be a computable sequence of the pairs $(p,q)$. I'm not convinced that can be done though. – 2012-01-22
-
0You don't need a computable sequence of $(p,q)$'s. Given any individual $p/q$, you can code it up in $\le(2/\beta+o(1))n$ bits, and, for large enough $n$, this will violate the incompressibility of the first $n$ bits of $\Omega$. So, you just need to pick one approximant which has large enough denominator. – 2012-01-22
-
0Where did you use the fact that there are infinitely many pairs $(p,q)$? What is $m$? – 2012-01-22
-
0$m=\lfloor{(2^np/q)-\frac{1}{2}}\rfloor$. The fact that there are infinitely many pairs $(p,q)$ is used to establish that there exists one such pair with large enough $q$. – 2012-01-22
-
0Even though I don't understand your answer yet, I will award you the bounty since its time is running out and you gave the question serious attention, which is what the bounty was for. – 2012-01-23