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.

  • 1
    $\begingroup$ So you want a number which is interesting or useful for some reason other than because it's non-computable? $\endgroup$
    – Jack M
    May 29 '14 at 22:02
  • 1
    $\begingroup$ Also, this section on Wikipedia seems relevant. If the answer to the titular question is "yes", it would seem there's no answer to this question. $\endgroup$
    – Jack M
    May 29 '14 at 22:07
  • 1
    $\begingroup$ Second question: when you mention the idea "all the reals that are needed in practice are computable," what do you mean by "in practice"? The practice of what? $\endgroup$ May 29 '14 at 22:19
  • 2
    $\begingroup$ How about $0^\sharp$ then? $\endgroup$ May 29 '14 at 22:36
  • 4
    $\begingroup$ $0^{\sharp}$ has the problem, of course, that it might not exist... :-) More seriously, the fact that we can meaningfully talk about 'worlds' where the computable reals are the only ones that exist means that any examples are bound to seem at least somewhat artificial. $\endgroup$ May 29 '14 at 22:58

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

  • 2
    $\begingroup$ Exactly!${}{}{}{}$ $\endgroup$
    – dtldarek
    May 30 '14 at 0:48
  • $\begingroup$ Is there a "natural" non-recursive set of positive integers then? $\endgroup$
    – Conifold
    May 30 '14 at 1:39
  • 1
    $\begingroup$ @Conifold: There are r.e. sets that are not recursive. The most "natural" one is probably the set of codes of proofs from PA. $\endgroup$
    – UserB1234
    May 31 '14 at 18:14
  • 1
    $\begingroup$ @Abhishek: (1) Yes, I emphasize "particular" to rule out constructions that simultaneously produce many reals each of which is noncomputable. The cardinality argument showing not all reals are computable is the epitome of this. For (2) I will add two examples to the answer. $\endgroup$ Jun 2 '14 at 15:40
  • 1
    $\begingroup$ @CarlMummert I would include also continued fractions (my favorite). $\endgroup$
    – dtldarek
    Jun 4 '14 at 20:03

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$

  • $\begingroup$ I was going to give this answer with Goodstein's theorem :) $\endgroup$
    – Ryan Reich
    May 30 '14 at 1:20
  • 2
    $\begingroup$ @RyanReich And how your sequence would look like? As far as I know, the Goodstein's sequence is computable. $\endgroup$
    – dtldarek
    May 30 '14 at 8:56
  • $\begingroup$ Of course you meant to write $f$ rather than $g$. $\endgroup$
    – r.e.s.
    Jun 1 '14 at 22:48
  • $\begingroup$ @r.e.s. Yes, thank you for noticing. $\endgroup$
    – dtldarek
    Jun 1 '14 at 23:31
  • $\begingroup$ Thanks @dtldarek . Your parametrized construction of an uncomputable real is perhaps the most general one I've seen so far. Also, you pointed out holes in my definition of "natural". $\endgroup$ Jun 4 '14 at 19:31

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.