9
$\begingroup$

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

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

1 Answer 1

8
+50
$\begingroup$

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

$\endgroup$
5
  • $\begingroup$ 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. $\endgroup$ Commented Jan 22, 2012 at 4:36
  • $\begingroup$ 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. $\endgroup$ Commented Jan 22, 2012 at 10:38
  • $\begingroup$ Where did you use the fact that there are infinitely many pairs $(p,q)$? What is $m$? $\endgroup$ Commented Jan 22, 2012 at 14:09
  • $\begingroup$ $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$. $\endgroup$ Commented Jan 22, 2012 at 19:46
  • $\begingroup$ 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. $\endgroup$ Commented Jan 23, 2012 at 4:44

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .