1
$\begingroup$

I was glancing over wikipedia's entry on transcendental numbers, where it said (with a citation I cannot verify):

Chaitin's constant (since it is a non-computable number)

It is not at all obvious to me that since it is not computable therefore it is transcendental. Part of the proof of the number being an $\Omega$ is to show it encodes halting probabilities. But in my mind it seems that it is possible there could be an algebraic irrational number which did encode this, but sadly we would never be able to prove that this number was an $\Omega$ number. Is there a relatively simple reason why this backdoor ruled out?

Thus the question:

Why can't it be that some polynomial has a zero which is an $\Omega$ number for some machine, even though there could be no proof that it is such a number. How do we know that such $\Omega$ numbers are in fact transcendental?

Post-comment edits:

(1) I understand algebraic numbers are computable. And I understand that by modus tollens uncomputable numbers are not algebraic. The question I have is with the role "uncomputable" plays here. Because in the case of $\Omega$ we define the bit sequence by a very specific method, which very specifically is not computable, in the sense that no algorithm can decide the halting problem, so no algorithm can yield all bits of an $\Omega$. But for any arbitrary sequence of digits we can write a program to enumerate those digits. So to my mind the problem is more like, we cannot take a number of demonstrate it is an $\Omega$ number because to do so would require being able to compute that $\Omega$ number and we already know we cannot. But then we cannot say that the bit sequence given by the some binary expansion isn't an $\Omega$. Which, to me, actually leaves room for $\Omega$ to be an algebraic, but we'd never know, because even though we could compute these bits, we'd never have any inkling that they encoded the halting probabilities for machine $M$.

Please understand I'm not trying to disprove the statement. I'm trying to understand the statement.

$\endgroup$
  • 3
    $\begingroup$ All rationals and algebraic numbers are computable, and as a consequence of this any uncomputable number is transcendental. $\endgroup$ – Joppy Apr 27 '17 at 21:09
  • $\begingroup$ Joppy, restating the very point in contention is not very helpful. I cannot compute arbitrary digits of Avogadro's constant because of a lack of information—information I cannot possibly obtain (just like digits of $\Omega$). Have I proved to your satisfaction that Avogadro's constant is transcendental? $\endgroup$ – law-of-fives Apr 27 '17 at 21:21
  • $\begingroup$ I was pointing out the fact that the number in question is transcendental is a consequence of it being uncomputable - perhaps I misunderstood your question. There is a simple reason that algebraic numbers are computable, which is that given a polynomial $P(x)$ and some interval $[a, b]$ containing the root, you can use approximation algorithms (such as Newton's method, or bisecting the interval) to churn out better and better rational approximations of the root. $\endgroup$ – Joppy Apr 27 '17 at 21:38
  • $\begingroup$ @Joppy ""I was pointing out the fact that the number in question is transcendental is a consequence of it being uncomputable" That is the question. Why is this relationship necessary? $\endgroup$ – law-of-fives Apr 27 '17 at 21:44
  • $\begingroup$ @Joppy this is not quite enough, since we can find better and better approximations of $\Omega$ too (just not with any decidable amount of precision). But we can say that uncomputable numbers are transcendental because there is an algorithm to determine the $n^{\text{th}}$ bit of an algebraic number. Or because there is an algorithm to decide if it lies within any given range. $\endgroup$ – Dan Brumleve Apr 27 '17 at 21:47
5
$\begingroup$

There are two questions here. The first, from the post, is to explain why algebraic numbers are computable; the second, from the comments, is to explain why the OP's argument does not show that Avogadro's constant is transcendental.

Let me tackle the second one first; it gets at a common confusion about computable numbers. When we say a number is computable, we don't mean that we know an algorithm which enumerates its decimal digits, we merely mean that there is some algorithm which does this. For example, let $x=1$ if the Riemann hypothesis is true and $x=2$ otherwise. Then I have no idea what $x$ is - in particular, I don't know a specific program which computes it - but I do know that it's computable: either the "just output $1$" program or the "just output $2$" program computes it. The fact that I don't know which one does the job, while interesting, is irrelevant.

So think back to what you said about Avogadro's number. All you argued was that we can never know with certainty what program computes it; however, there's no a priori reason that some program couldn't just happen to compute it. So it might be computable, even if we have no way of determining exactly what program does the job - in particular, there's no reason (at the moment) to believe that it is irrational.

By contrast, the proof that $\Omega$ is incomputable really shows that no program can compute $\Omega$, full stop, not just that we'll never be able to prove that a specific one does. In particular, you ask whether we could get around the proof by not assuming that we ever manage to prove what program works, but this won't get you around the proof, since it never assumes we ever prove which one works!


OK, now onto the main question: why are algebraic numbers computable?

Alright, first observation. Suppose $a$ is a zero of some nonconstant polynomial $p(x)$. Because it's nonzero, $p$ has only finitely many zeroes; in particular, I can find a pair of rationals $q_0$ and $q_1$ such that $q_0<a<q_1$ and $a$ is the only zero of $p$ between $q_0$ and $q_1$ inclusive. This gives me a pretty good description of $a$: "The unique zero of $p$ in $[q_0, q_1]$."

This isn't all the way to a computation of $a$ yet, but it should make it plausible that $a$ is going to be computable. Next up is some basic calculus. The intermediate value theorem tells us that there are four possibilities for what $p$ does in the interval $(q_0, q_1)$:

  • $p(x)<0$ for $x<a$, $p(x)<0$for $x>a$.

  • $p(x)<0$ for $x<a$, $p(x)>0$for $x>a$.

  • $p(x)>0$ for $x<a$, $p(x)<0$for $x>a$.

  • $p(x)>0$ for $x<a$, $p(x)>0$for $x>a$.

(Remember that $a$ is the only zero of $p$ in $(q_0, q_1)$!) Note that cases (3) and (4) are basically the same as (2) and (1), respectively. So I'll just do cases (1) and (2). Finally, for simplicity let's assume $q_0=0$ and $q_1=1$.

Let's first deal with possibility (2) (and by extension, (3)).Let's find the first digit of $a$! We compute $p(0.0), p(0.1), p(0.2), ... , p(0.9), p(1)$ - or rather, we just check to see whether each is positive or negative (exercise: show that we can computably do this!). Going from $0.0$ to $1.0$, at some point we switch from positive to negative - say, $p(0.4)<0$ but $p(0.5)>0$. Then we know that $a\in (0.4, 0.5)$ - and the first digit of $a$ is "$4$"! Now we repeat this trick inside the interval $(0.4, 0.5)$ - we look at $p(0.40), p(0.41), ..., p(0.49), p(0.50)$. Going forward like this, we can compute each of the digits of $a$.

Possibility (3) is identical, but with "positive" and "negative" flipped.

What about possibility (1) (and similarly, (4))? This is a bit trickier - there's no obvious "sign change" to look for. But we have a neat observation . . . if we're in case (1), then $a$ is a zero of $p'(x)$, and (since $p$ is nonconstant and has at least one zero) the polynomial $p'$ is nonconstant! So now we switch from looking at $p$ to looking at $p'$: in terms of $p'$ (and picking new $q_0$ and $q_1$ if necessary), is $a$ in case (1), (2), (3), or (4)? If we land in case (2) or (3), we work as above; otherwise, we go to $p''$! And so on. At some point we have to land in case (2) or (3) (why? HINT: take enough derivatives of a polynomial and you get the zero function ...), and then we argue as above.

So we've concluded that there always is some program computing $a$. Note that we seem to have made a lot of choices:

  • What do we choose as $q_0, q_1$?

  • If we go down to $p'$, what do we choose for $q_0', q_1'$ etc.?

  • How many derivatives do we have to take before we land in case (2) or (3)?

However, the sum total of all the choices we make can be coded by a single natural number (the hardest part of this is showing that a finite sequence of rationals can be effectively represented by a single natural number, but that's not hard), so given that number $\alpha$ we can write a program $\Phi_\alpha$ which computes $a$. And in turn, this means we know that for some $\alpha$, $\Phi_\alpha$ computes $a$ - even if we don't know which $\alpha$ does the job, this means $a$ is computable.

$\endgroup$
  • $\begingroup$ Thank you for your response. You say, "the 'just output 1' program". There is some fact of the matter about an $\Omega$, for instance whether it is greater or less than some number, it's difference from 2, what its $2^{17}$ bit is, etc. We just cannot compute this. So god comes down and hands you a number, and tells you it is an $\Omega$. Could it be proven this was an $\Omega$? The Avogadro analogy is not the best in the world on short notice, I admit. I may try to think of a better analogy to explain my question since it seems to not be understood. $\endgroup$ – law-of-fives Apr 27 '17 at 23:32
  • $\begingroup$ @law-of-fives I'm not really sure what you're asking. The "just output 1" program is an actual program which you can write (it's quite simple); there is no "just output $\Omega$" program (try writing it). The whole point of the proof is that there is no program which computes $\Omega$, full stop. I'm not sure how a "fact-of-the-matter" comes into this at all; there is a fact of the matter about every real number, computable or otherwise, and that has no bearing on the (in)computability of the number. (continued) $\endgroup$ – Noah Schweber Apr 27 '17 at 23:35
  • $\begingroup$ Re: the god question, the problem is that this is very imprecise - until you formalize it more rigorously, it can't be answered. Here's one thing you might try to do: start with some appropriate theory, add a constant symbol $c$, and the following further axioms: "$c<q$" whenever $q$ is a rational bigger than $\Omega$, and "$c>q$" whenever $q$ is a rational smaller than $c$. This theory $T$ cannot prove that $c=\Omega$ (in particular, we can find a specific rational $q_T$ such that $T$ can't decide whether $\Omega>q_T$ or $\Omega<q_T$!). If this is not what you meant, you'll need to clarify. $\endgroup$ – Noah Schweber Apr 27 '17 at 23:38
  • $\begingroup$ thank you for those responses, yes. I think you are close to helping me understand this. I have edited the original question with what I hope are more clarifying remarks to show me where I am going wrong. $\endgroup$ – law-of-fives Apr 27 '17 at 23:45
  • $\begingroup$ @law-of-fives The statement "But for any arbitrary sequence of digits we can write a program to enumerate those digits." is wrong - the whole point is that there are sequences of digits which you can't write a program for. You can write a program to enumerate any finite sequence of digits, but that's not the same. (Similarly, not every real is definable in any nice way - indeed, most aren't!) $\endgroup$ – Noah Schweber Apr 27 '17 at 23:59

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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