Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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$?

share|improve this question
    
The 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$. –  joriki Dec 13 '11 at 20:25
    
Have you made any progress on this question? I like it and think it deserves more attention. –  Quinn Culver Jan 14 '12 at 20:37
    
@joriki It would be interesting though, if the irrationality measure was independent of the machine used. –  Quinn Culver Jan 14 '12 at 20:59
    
@QuinnCulver Unfortunately, I still do not know the answer. –  Vladimir Reshetnikov Jan 15 '12 at 21:18
    
@VladimirReshetnikov Why not offer a bounty then? –  Quinn Culver Jan 16 '12 at 14:20

1 Answer 1

up vote 6 down vote accepted
+50

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|<q^{-\beta}$; since $\Omega\in(0,1)$, such a pair will have $0\le p\le q$.

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 (**).

share|improve this answer
    
It seems you need for there to be a computable sequence of the pairs $(p,q)$. I'm not convinced that can be done though. –  Quinn Culver Jan 22 '12 at 4:36
    
You 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. –  David Moews Jan 22 '12 at 10:38
    
Where did you use the fact that there are infinitely many pairs $(p,q)$? What is $m$? –  Quinn Culver Jan 22 '12 at 14:09
    
$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$. –  David Moews Jan 22 '12 at 19:46
    
Even 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. –  Quinn Culver Jan 23 '12 at 4:44

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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