22
$\begingroup$

All the online resources that I've seen on uncomputable numbers assume that they're all irrational. But this doesn't seem to be required by the definition. Wikipedia, for example, says that "[un]computable numbers are the real numbers that can [not] be computed to within any desired precision by a finite, terminating algorithm."

But doesn't this also describe the outputs of uncomputable functions? Busy_beaver(6) cannot be computed by any finite terminating algorithm, yet it's an integer. (Well ok, maybe the 6th is still computable and they only become uncomputable later. But that's not relevant to this question.)

Perhaps the issue here is the definition of "number". In the context of uncomputable numbers, people are interpreting Busy_beaver(6) as a statement of "we don't know what number is the result of this function", rather than a specific number. After all, whatever Busy_beaver(6) is, that number could also be computed some other way. If Busy_beaver(6) is, say, 10^20000, there's certainly a finite terminating algorithm that outputs 10^20000, even if we have no way of knowing that that number is also the result of Busy_beaver(6).

But this seems to conflict with how people talk about "numbers" in other contexts. You can define two large numbers that are the results of computable functions, (like Graham's Number or TREE(3) or whatever), and people agree that those specify a single unambiguous number, even if we don't know if two of them are equal or know their exact decimal expansion.

For that matter, how do we know that Chaitin's Constant isn't the result of any finite terminating function? The argument given on the Wikipedia page only proves that we can never compute what number is Chaitin's Constant, but it doesn't prove that Chaitin's Constant is itself not the result of any other unrelated function. (For example, how can you prove that Chaitin's Constant isn't pi/4? Maybe it is, we'd just never know.)

Clearly I'm very confused about what types of statement count as clearly defining a single number. Help?

$\endgroup$
6
  • 1
    $\begingroup$ Chaitin's constant (strictly speaking there are inifnite many such constants) is not only uncomputable , it is a random number (in the sense that it cannot be significantly compressed) , $\frac{\pi}{4}$ has neither of those properties. The decimal expansion of Graham's number can of course not be determined , but usually very large number can be compared (usually one is vastly larger). This can of course be extremely difficult however. $\endgroup$
    – Peter
    Oct 11, 2022 at 12:01
  • 3
    $\begingroup$ "If Busy_beaver(6) is, say, 10^20000": FWIW, you may like to know that $BB(6) > 10\uparrow\uparrow 15.$ $\endgroup$
    – r.e.s.
    Oct 11, 2022 at 14:08
  • 2
  • 1
    $\begingroup$ "Well ok, maybe the 6th is still computable and they only become uncomputable later. But that's not relevant to this question." Maybe this is the crux of your misunderstanding? $BB(n)$ is a computable number for all $n$, but since you'd need a different algorithm for each $n$, there's no single algorithm that computes $BB(n)$ for all $n$. $\endgroup$ Oct 12, 2022 at 20:54
  • 1
    $\begingroup$ @MartianInvade This question is about the two different definitions of the concept of "computability", one relating to numbers and one relating to functions. In the sentence you quoted, I was referring to functions. The busy beaver function can be computed for some inputs, but not all. BB(6) is a computable number, but we don't know whether it can actually be computed as the result of BB(). $\endgroup$
    – Isaac King
    Oct 13, 2022 at 4:28

2 Answers 2

43
$\begingroup$

Edit: There's an additional subtlety I feel like I've glossed over which I'd like to describe in more detail. First, we can write down a predicate $\text{Computes}(T, r)$ (in first-order ZF, to be specific) which given a Turing machine $T$ and a real number $r$ asserts that $T$ computes $r$.

Now, "$r$ is computable" is defined to mean "$\exists T : \text{Computes}(T, r)$." So an important part of the potential confusion here has to do with the standard meaning of $\exists$ in classical first-order logic: importantly, proofs of existence are not required to be constructive, in the sense that a proof that $\exists x P(x)$ is not required to proceed by constructing an explicit element $x$ and then verifying that it satisfies $P(x)$. So it is possible to prove nonconstructively that a real number, such as $BB(6)$, is computable, without constructing an explicit Turing machine computing it.

You might consider this unsatisfying and a bad way to define "computable," or at least you might want to be able to refer to some notion of "explicit computability." (If so you might be interested in reading about constructivism.) Here's a simple way to do it: we just define an explicit computation of a real number $r$ to be a construction of a Turing machine $T$ satisfying $\text{Computes}(T, r)$ (one must supply both the Turing machine $T$ and a proof that it computes $r$). In other words, to prove that a real number $r$ is "explicitly computable" one must exhibit the Turing machine computing it, rather than only proving that some such Turing machine exists.

Note, however, that I really do want to alter the grammar here to "explicit computation" rather than "explicitly computable." This is not a definition of a class of real numbers satisfying a logical condition; this notion of "explicit computability" depends on which Turing machines have been written down so far, and in particular it changes over time if some new Turing machine is written down which explicitly computes some number that had not yet been previously computed. Also, only finitely many real numbers have been explicitly computed in this sense since only finitely many Turing machines have been written down. Worse, only finitely many real numbers can be explicitly computed in this sense, since the universe (as far as we know) is not arbitrarily large and cannot fit descriptions of arbitrarily large Turing machines in it.

However, this is a way to make precise the sense in which we don't know $BB(6)$: nobody has yet written down a Turing machine computing it, so it has not been explicitly computed in the sense above.

(Original answer follows from here.)


All the online resources that I've seen on uncomputable numbers assume that they're all irrational.

This isn't an assumption, it's a theorem. Every rational number is computable because there exists a program which prints out the digits of any rational number. Similarly, because we can compute the roots of a polynomial with rational coefficients to arbitrary precision, every algebraic number is computable, so uncomputable numbers are transcendental.

But doesn't this also describe the outputs of uncomputable functions? Busy_beaver(6) cannot be computed by any finite terminating algorithm, yet it's an integer.

We need to distinguish carefully here between objects and descriptions of objects. We have no idea what number $BB(6)$ is, but if you believe that $BB$ is a well-defined function, whatever number $BB(6)$ is, that number is trivially computable, namely by a program which prints out its digits. We simply don't know which program this is!

This issue actually has nothing to do with $BB$ not being computable, it is really about the difference between numbers and descriptions of numbers. For example, consider the integer which is equal to $0$ if the Riemann hypothesis is false and $1$ if the Riemann hypothesis is true. Whichever number this is, it is again trivially computable, by either the program which prints $0$ or the program which prints $1$. We just don't know which program is correct!

(Less trivially, there is a single computer program, which in principle we can write down explicitly right now, which prints $0$ if the Riemann hypothesis is false and prints $1$ if it's provable in ZFC. This is because we can search through the nontrivial zeroes of the zeta function and verify that they have real part $\frac{1}{2}$ (it requires some nontrivial complex analysis to show that this is possible), and we can also search through proofs of the Riemann hypothesis in ZFC. However, this program would run forever in the unlikely event that the Riemann hypothesis is true but independent of ZFC.)

For that matter, how do we know that Chaitin's Constant isn't the result of any finite terminating function? The argument given on the Wikipedia page only proves that we can never compute what number is Chaitin's Constant, but it doesn't prove that Chaitin's Constant is itself not the result of any other unrelated function. (For example, how can you prove that Chaitin's Constant isn't pi/4? Maybe it is, we'd just never know.)

No, the argument on Wikipedia proves that the digits of Chaitin's constant cannot be printed by any Turing machine (this is what it means for a specific number to not be computable), because if it could then that Turing machine also solves the halting problem. Since the digits of $\frac{\pi}{4}$ (or whatever other computable real you like) can be printed by a Turing machine, it cannot be equal to Chaitin's constant. This is a genuinely different situation from the $BB(6)$ example, which can be printed by an unknown Turing machine.

The following analogy may be helpful: suppose somehow that someone proved by contradiction that $\pi + e$ is algebraic (this number is not known to be transcendental). This would mean that there is some rational polynomial $f(x)$ such that $f(\pi + e) = 0$. This would be true even if the proof does not produce $f$, so we don't know what it is. So this unknown polynomial would be analogous to the unknown Turing machines above.

$\endgroup$
11
  • 2
    $\begingroup$ "The argument on Wikipedia proves that the digits of Chaitin's constant cannot be printed by any Turing machine (this is what it means for a specific number to not be computable), because if it could then one could use that Turing machine to solve the halting problem." I don't see how that follows. In order to use 𝜋/4 to solve the halting problem, you would need to know that 𝜋/4 is Chaitin's constant. If all you know is that Chaitin's constant is some computable number, but you don't know which one, that doesn't help you solve the halting problem. $\endgroup$
    – Isaac King
    Oct 11, 2022 at 4:21
  • 14
    $\begingroup$ @IsaacKing: it doesn't help you solve the halting problem, but it proves that the halting problem is solvable by some Turing machine, which is already a contradiction. The unsolvability of the halting problem doesn't stop applying to a Turing machine just because we don't happen to know what it is! $\endgroup$ Oct 11, 2022 at 4:25
  • 1
    $\begingroup$ But I take your point that there's a subtlety with my original wording, which I've edited to hopefully make clearer. $\endgroup$ Oct 11, 2022 at 4:30
  • 1
    $\begingroup$ There may, however, be a series of programs which print increasingly precise approximations to Chaitin's constant. Just not one program which prints the entire infinitely-long number. $\endgroup$
    – user253751
    Oct 11, 2022 at 16:29
  • 6
    $\begingroup$ @user253751: that's true of every number, because every number has arbitrarily good rational approximations. But there's no computable way to describe such a series of programs. $\endgroup$ Oct 11, 2022 at 16:33
5
$\begingroup$

I just want to add to Qiaochu Yuan's excellent answer above with a concrete example of the distinction between computable number and computable function

Consider $BB$: this is a well-defined natural valued function, so for any $n$, there is a single natural number that is the value of $BB(n)$.

Also, observe that for any natural number there is a trivial Turing machine that outputs that number. The intuition is basically that the number is encoded in the Turing machine and is copied to the output tape when the machine is run. I'm a programmer, so I imagine that the number is essentially a constant in the source code of the machine, and the machine outputs that constant without having to actually compute anything.

So, $BB(6)$ is computable — there is a (trivial) Turing machine that outputs it in finite time.

However, for the function $BB$ to be computable, there would need to be a Turing machine that takes $n$ as an input and outputs $BB(n)$ for all $n$. Clearly from the definition of $BB$, the Halting Theorem shows that there is no such machine.

So, for any fixed $n$, the value $BB(n)$ is a computable number. However the function $n\mapsto BB(n)$ is not itself computable.

$\endgroup$

You must log in to answer this question.

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