Can You Compute This?

The definition of a computable number entails that for each of the countable (binary) digit, there is a finite process to decide whether it is a zero or a one.

It turns out (as I proved above) that the number of computable numbers is not greater than the number of finite "programs" one can write, which in turn is no greater than the set of natural numbers. (This kind of infinity is "countable".)

On the other hand, it can be proven that the number of real numbers (even just those between 0 and 1) is uncountable , essentially larger than the set of natural numbers.

Therefore, there are (uncountably many) more real numbers than computable numbers. These real numbers exist, but there is no way to describe them or calculate them with infinite precision.

I would argue that the set of computable numbers is greater than the set of algebraic numbers over the rationals $\mathbb Z$ . (An algebraic number is a solution of a polynomial equation.) After all, an algebraic number can be obtained by solving a polynomial equation using successive approximations. Also, all sines, cosines, tangents, etc., inverse sines, etc., logarithms are in principle computable with a finite algorithm; this includes irrational, non-algebraic numbers such as $\pi$ , $e$ , and $\ln 2$ . Yet all these numbers form a countable set, therefore much smaller than the set of all reals.

Here is a recipe to find such a number.

Let $U = [0,1]$ be the uncountable set of all reals between 0 and 1.

Let $\mathbb A$ be the countable set of all finite algorithms as described in this problem. For an algorithm $A$ , let $c(A)$ be the number it describes.

Let $X = U - c[\mathbb A]$ be the real numbers between 0 and 1 that are not computable. Since an uncountable is strictly greater than a countable set, $X$ is not empty.

Invoking the Axiom of Choice, let $x \in X$ . Then $x$ is the desired, non-computable number.

I cannot give you more details. Any constructive algorithm to generate or test $x$ for a given property in a finite number of calculation steps would make it computable.

(What exactly makes our $x$ non-computable? Is the set of non-computable numbers paradoxical? Why or why not?)

Your program would have to generate this enumeration as it is going; we cannot assume that such a list is available beforehand!

1
2
3
4
5
6
7
8

define CantorDigit(n):
   a = 0
   for i = 1 to n-1
      a++ until IsValidAlgorithm(a)

   dig = RunAlgorithm(a, n)   // run program with bitcode 'a' for digit 'n'
   dig = 1 - dig
   return dig

Now suppose that this program has bitcode $a^\star$ , and is the $n^\star$ th valid algorithm we encounter. Executing dig = RunAlgorithm(a*, n*) essentially means running CantorDigit(n*) recursively. Thus the program will find itself in an infinite loop! If it could be decided beforehand whether an algorithm would give an answer in a finite number of steps, $a^\star$ would simply be rejected as not a valid algorithm; but since the "stopping problem" is unsolvable, we must conclude that any attempt to execute your algorithm would result in a hang-up, or infinite loop.

Are you aware of the different cardinality ? We can have an infinite list of numbers, but they could still be countably infinite. For example, the integers are a countable set. Using your example of $\frac{ n}{ 2^k }$ , this is still a countable set (indexed by $k$ ).

We need to add "much much more" in order to go from countable to the uncountable.

We could make Turing-completeness the definition of computability--it is the classical and best rigorous way of doing so. I did not want to go into these technical details.

Your algorithm will not produce a computable number, but get stuck in an infinite loop or otherwise undefined.

First of all, while the list of all computable numbers "exists" in a mathematical sense, your algorithms do not have access to this list; it cannot be stored as part of the program because it is doubly infinite, and it cannot be generated in its entirety in finite time. This is why the Cantor argument does not apply in the same way.

What you do have is a way to interpret any integer $N$ as an algorithm (computation), so that in principle you can calculate the $n$ th digit of the $N$ th number in finite time.

Now suppose that your clever, Cantor-style algorithm is encoded in integer $N^\star$ . It applies algorithm 1 to generate digit 1 of the first number; you flip it. It applies algorithm 2 to generate digit 2 of the second number; you flip it. And so on. This may go well, until you get to digit number $n^\star = N^\star$ . In order to find this digit, your algorithm must execute algorithm $N^\star$ (i.e. itself!) to generate the $n^\star$ th digit-- precisely the process that you are currently working on. Thus we have a recursive application of the algorithm, which will never finish.

The crux is that an algorithm FindDigit(n) may not only return 1 or 0, but can also remain undecided, for instance because it never stops. It is well-known that one cannot escape the "halting problem" (i.e. any function DoesItStop(N) may get into an infinite loop).

That's a great question!

You are computing the digits $b_i$ from some enumeration $a_{i,n}$ , where represents the $i$ th digit of the $n$ th computable number. However, if there is no way to compute the digits $a_{i,n}$ , then you cannot computet $b$ either. The main issue is "there is a representation between them and the natural numbers", where you implicitly assume that this function is computable.

However, there is no computable function $f(i,n)$ that satisfies the following conditions:

• For every $i$ , the function $n \mapsto f(i,n)$ gives a decimal expansion of a real number - This means that the numbers are real. We could require that the output is an integer from 0 to 9.
• For any $i, n$ , $f(i,n)$ eventually returns some output - This means that the real numbers are computable.
• For every computable real $a$ , there is some $i$ with $a_n = f (i,n)$ for all $n$ - This means that all the computable numbers are in the list.

In fact, the diagonalization argument is how we prove that no such $f(i,n)$ exists. Specifically, if such a function exists, we can take the cantor-diagonalization to get another computable real, which contradicts the claim that every computable real is on the list.

Note: In the event that this has/hasn't blown your mind, think about why this counter-counter-argument doesn't apply to show that the real numbers are countable.