Is it possible to prove the existence of two real numbers $a, b$ that have the property that it is uncomputable whether or not $a<b$?
Asked
Active
Viewed 116 times
0
-
1That depends on how you're allowing me to specify real numbers! – Qiaochu Yuan Jun 08 '14 at 18:39
-
Is it cheating to let $a=1$, and $b=2$ if the continuum hypothesis is true, $b=0$ if not? – Harald Hanche-Olsen Jun 08 '14 at 18:40
-
No, I think that's a brilliant solution! – Jostein Trondal Jun 08 '14 at 18:43
-
Or? Does $b$ exist, Harald? – Jostein Trondal Jun 08 '14 at 18:49
-
For a number to exist, shouldn't it be a specific number? If it is uncomputable whether b is 0 or 2, then it is not a specific number. The uncomputability should be if $a<b$. – Jostein Trondal Jun 08 '14 at 19:05
1 Answers
4
No, it cannot be proved, because no such numbers exist; that is, for any two real numbers $a$ and $b$, the value of the function $f_{<}: {\Bbb{R}}^2\to\{0,1\}$ such that $$f_{<}(a,b) = \begin{cases} & 1 \ \ \text{ if }\ a < b\\ & 0 \ \ \text{ otherwise } \end{cases}$$ can be computed for those particular $a$ and $b$. This is so because, regardless of how the two reals are supposed to be represented as input, the following two programs exist: program $P_0$ does nothing but output $0$ and halt, and program $P_1$ does nothing but output $1$ and halt. Consequently, one of these two programs correctly computes the number $f_{<}(a,b)$. (That we may not know which of these two programs is the correct one is not relevant to its existence.)
However, note that in reasonable models of real computation, the function $f_{=}: {\Bbb{R}}^2\to\{0,1\}$ such that $$f_{=}(a,b) = (1-f_{<}(a,b))(1-f_{<}(b,a)) = \begin{cases} & 1 \ \ \text{ if }\ a = b\\ & 0 \ \ \text{ otherwise } \end{cases}$$
is uncomputable (see a proof here), and hence the function $f_{<}$ is uncomputable -- in contrast to the computability of any single number such as $f_{<}(a,b)$.
-
Forgive me if I am wrong about what I am about to write in the following (I have no experience with computability other than reading a bit about it).
In my mind, the fact that we may not know which of $P_0$ and $P_1$ is the correct one, is exactly why we haven't computed anything. We don't know the answer. Information about the truth exists in the system of definitions, but this truth cannot reach the user, and by this, has not been computed.
How is my reasoning wrong?
– Jostein Trondal Jun 15 '14 at 19:41 -
1This is a subtle point: computability may be proved nonconstructively, without any explicit description of a specific algorithm; rather, what's required is proof of the existence of the relevant algorithm. (This is also illustrated by the last two examples at https://en.wikipedia.org/wiki/Computable_function#Examples .) – r.e.s. Jun 16 '14 at 01:58
-
Aha! Thanks for clearing that up!. Anyway, nonconstructive computability feels like an oxymoron to me... – Jostein Trondal Jun 16 '14 at 21:35
-
1It isn't "nonconstructive computability", it's "nonconstructive proof of computability". – r.e.s. Jun 18 '14 at 17:26