a "natural" real number that is not computable

Question

Most of the examples of non-computable real numbers use some kind of a diagonalization construction over some turing computable model of computation. See Are there any examples of non-computable real numbers?.

I want to know if there are "natural" real numbers that are not computable. I'm having difficulty in formalizing what I mean by "natural". Here is a necessary condition for naturality: The description of that number should not mention any turing computable model of computation.

Ideally, this number should have existed in the literature even before Turing invented Turing machines. Somehow this is analogous to the way Solomon Feferman says:

Finally, we must take note of the fact that up to now, no previously (w.r.t. the day Gödel announced his incompleteness theorems) formulated open problem from number theory or finite combinatorics, such as the Goldbach conjecture or the Riemann Hypothesis or the twin prime conjecture or the P=NP problem, is known to be independent of the kinds of formal systems we have been talking about,not even of PA.

in http://math.stanford.edu/~feferman/papers/newaxioms.pdf. The parts in parenthesis have been added by me to put his quote in proper context. My question was partly motivated by this quote.

Answer 1

The correct intuition is that there are no examples of particular natural noncomputable real numbers.

One significant obstacle to finding an example is that computability is more directly about sets of naturals, not about real numbers. Most examples of noncomputable real numbers are constructed by coding a noncomputable set of naturals into a real number. The coding method is always somewhat arbitrary, which goes against the uniqueness of the real number being constructed.

Examples of coding methods

Here are two examples of different coding methods. The trouble is that the best way of encoding information into a real number seems to be to use the decimal (or binary, or base 813) expansion in some way, but there is no obvious "canonical" or "best" way to do this. Suppose I have an infinite set $A$ of natural numbers. I can make a real number $r$ that "computes" $A$ in several ways:

• I can make it so that $r \in [0,1]$ and the decimal expansion of $r$ is the characteristic function of $A$. I could also do this so that $r \in [0,1]$ and the binary expansion of $r$ is the characteristic function of $A$. Neither of these seems more canonical than the other.

• I can make it so that the "gaps" between the nonzero digits in the binary expansion of $r$ tell me about $A$. So if $A = \{1, 3, 5, \ldots\}$ then I take $$ r = 0.1010001000001\ldots$$

Answer 2

I'm not aware of any previously known number which is not computable, but one can easily construct one that does not involve any Turing machines or any other similar ways of computation (e.g. $\lambda$-terms, grammars and so on).

To give an example, take a look at Wikipedia's list of undecidable problems and pick one you like.

For example, we could take the matrix mortality problem and make the inputs into a sequence, e.g. pick your favourite bijection $\mathbb{N} \to \mathbb{Z}^{2\cdot 15^2}$ and create a sequence $(a_n)_{n \in \mathbb{N}}$ of pairs of integer $15 \times 15$ matrices. Then define $f : M_{15\times 15} \times M_{15\times 15} \to \{0,1\}$ as $f(A,B) = 1$ if there exists $k \in \mathbb{N}$ and function $h : \{0,..,k\} \to \{A,B\}$ such that $\prod_{i = 0}^k h(i) = \mathbf{0}$ and $f(A,B) = 0$ otherwise.

We can now define our number as $$\sum_{k \in \mathbb{N}}\frac{f(a_k)}{2^k}$$

and because matrix mortality problem is undecidable, then the above number is uncomputable.

I know this is not exactly what you were looking for, but perhaps it might help $\ddot\smile$