a "natural" real number that is not computable

Solution 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$$

Solution 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$