30
$\begingroup$

Every computable number is definable. However, the converse is not true. What is an example of a real number that is definable but that is NOT computable? I guess if it is there, we can "define" (describe) it, can't we?

$\endgroup$
  • 1
    $\begingroup$ Define in what language? $\endgroup$ – Asaf Karagila May 4 '15 at 15:47
  • $\begingroup$ As in the intro of this article. en.wikipedia.org/wiki/Definable_real_number $\endgroup$ – islamfaisal May 4 '15 at 15:53
  • $\begingroup$ I don't actually believe, philosophically speaking, in non-computable reals. $\endgroup$ – Kyle Strand May 5 '15 at 5:03
  • $\begingroup$ I don't know if integrals of some pathological functions can qualify as "non-computable " here. If yes, there are way too many examples. $\endgroup$ – Vim May 5 '15 at 7:52
  • 2
    $\begingroup$ @Wrzlprmft: You said "the smallest positive real number". I don't agree that there is one, not to say a unique one! So you cannot use it in a definition. =) $\endgroup$ – user21820 May 5 '15 at 12:10
25
$\begingroup$

Here is a non-computable real number: $$\sum_{i=1}^\infty 2^{-\Sigma(i)}$$ where $\Sigma$ is any busy beaver function.

$\endgroup$
  • 1
    $\begingroup$ But is it well-defined? $\endgroup$ – cfh May 4 '15 at 15:59
  • 4
    $\begingroup$ @cfh: Since the Busy Beaver function is a well-defined function, yes. How could it not be well-defined? $\endgroup$ – Asaf Karagila May 4 '15 at 16:04
  • 20
    $\begingroup$ The sum converges since it is bounded above by $\sum_{i\ge 1} 2^{-i}$, which is geometric. $\endgroup$ – vadim123 May 4 '15 at 16:07
  • 4
    $\begingroup$ @cfh: Busy Beaver grows faster than any computable function $\endgroup$ – Mehrdad May 4 '15 at 17:54
  • 3
    $\begingroup$ How does our knowledge that this sum cannot be computed prove that the number itself is not (coincidentally, and necessarily unbeknownst to us) computable via some other algorithm? $\endgroup$ – Kyle Strand May 23 '15 at 23:17
24
$\begingroup$

The point here is that definable real numbers are definable using the entire strength of might of the set theoretic universe; whereas computable real numbers are only allowed to access the natural numbers and their very very very rudimentary properties (since computable functions are only $\Sigma_1$ definable functions over $\Bbb N$).

Let $\varphi_n$ enumerate the sentences in the language of arithmetic. Now consider the real number whose $n$-th digit in the decimal expansion is $1$ if and only if $\Bbb N\models\varphi_n$, and $0$ otherwise. So it is a number in $[0,1]$.

This number is of course definable in the language of set theory, since the set of true sentences in $\Bbb N$ is definable; but it is not a computable real number since there is no computable function telling us what is true in $\Bbb N$ and what isn't (not even arithmetical, to be more accurate).


We can also take the following approach, as I suggest in the comments to the original question.

Note that every computable real lies in $L$, by absoluteness arguments (every computable functions lies there), and in $L$ there is a definable well-ordering of the reals (even with a $\Delta^1_3$ definition!), so there is a least real in the canonical well-ordering which is not definable.

Since the set "the real numbers which also lie in $L$" cannot change between models of $\sf ZF$ with the same ordinals, this set always has a canonical, definable well-ordering in any model of $\sf ZF$, and this indeed gives us a definition of a real number which is non-computable.


You can also argue that various generic reals are non-computable but definable, if you're willing to go this far as to consider different set theoretic universes (or at least one which can be seen as a nontrivial generic extension of some inner model).

For example Jensen reals are definable (they are the unique solution to a $\Pi^1_2$ predicate) but not computable.

Similarly, you can consider the iterated forcing that at the $n$-th step does the lottery sum between forcing $2^{\aleph_n}=\aleph_{n+1}$ and forcing $2^{\aleph_n}=\aleph_{n+2}$, at the limit step take a finite support limit, and consider the real number whose $n$-th decimal digit $1$ if and only if $2^{\aleph_n}=\aleph_{n+1}$, and $0$ otherwise.

This is a Cohen real which is definable, since it encodes the continuum below $\aleph_\omega$; but of course it is not computable by genericity arguments.

Note that this gives a very peculiar example of a real number, the one encoding the continuum function below $\aleph_\omega$. It is always definable, but in different models of $\sf ZFC$ it wil have different values, sometimes they will be computable (e.g. if $\sf GCH$ holds) and sometimes they could be non-computable (as above).

So this gives us a definition of a real number which is not provably computable and not provably uncomputable!

$\endgroup$
  • $\begingroup$ One step beyond! $\endgroup$ – rewritten May 4 '15 at 17:34
  • 2
    $\begingroup$ Well, you know what they say... to infinity and beyond! :-) $\endgroup$ – Asaf Karagila May 4 '15 at 17:39
  • 2
    $\begingroup$ I'd be happy to hear verbally about the mistakes in this answer! Silent downvotes might speak volumes, but it can often be in a foreign language, even more so when they are countered by many upvotes. $\endgroup$ – Asaf Karagila May 5 '15 at 10:00
  • $\begingroup$ Hmm... second downvote. I'd really love to hear some actual criticism. Although I can't help but feel that maybe the criticism begins and ends with "It was written by Asaf Karagila", which admittedly is not that constructive. But if anyone has any idea what's wrong with this answer, I'd be interested to hear about that! $\endgroup$ – Asaf Karagila May 5 '15 at 15:45
  • $\begingroup$ Could you elaborate on how you define a real number by doing those forcings? $\endgroup$ – Mario Carneiro May 6 '15 at 1:22
11
$\begingroup$

The probability that a random computer program will run forever is not computable. http://en.wikipedia.org/wiki/Chaitin%27s_constant

That some aspects of our concepts in this area are problematic is illustrated by the following example, which I learned from Hartley Rogers' book on computability: let $$ f(x) = \begin{cases} 1 & \text{if there is a sequence of }x\text{ consecutive 7s in the decimal expansion of }\pi, \\ 0 & \text{otherwise}. \end{cases} $$ This is computable! And there is an easy argument for its computability. And the algorithm for computing this function is really really simple. One can prove that easily, but no one knows, nor is it at all easy to know, which algorithm it is.

$\endgroup$
  • $\begingroup$ Could you elaborate what qualifies as a 'really really simple' for the algorithm of $f$? $\endgroup$ – orlp May 4 '15 at 18:03
  • 4
    $\begingroup$ It is either identical to g (x) = 1 for all x, or it is identical to h (x) = 1 if x ≤ n, and h (x) = 0 otherwise, for some value of n. In any case, it is very easy to compute. The only problem is that we don't know which one it is and what the value of n would be. $\endgroup$ – gnasher729 May 4 '15 at 18:09
  • 1
    $\begingroup$ @orlp : The algorithm is one of the following. If there is no longest sequence of consecutive $7$s, then always return $1$. If there is a longest such sequence, return $1$ if $x\le{}$the length of that longest sequence, and otherwise $0$. That gives you an infinite sequence of algorithms, each really simple. But WHICH one is the right one? No one knows. ${}\qquad{}$ $\endgroup$ – Michael Hardy May 4 '15 at 18:28
  • $\begingroup$ @MichaelHardy It is computable, but not nessesarily terminating. Just generate a moving window of size $x$ of the digits of $\pi$ and check if all of them are $7$. $\endgroup$ – NightRa Aug 28 '15 at 10:11
  • $\begingroup$ @NightRa : Computability as usually defined does not follow from your comment. ${}\qquad{}$ $\endgroup$ – Michael Hardy Aug 28 '15 at 14:45
7
$\begingroup$

The Chaitin's constant is a well defined number in computability theory, but it is not computable. But, about the concept of definable number see the answers to Definable real numbers.

$\endgroup$
7
$\begingroup$

If we consider an enumeration of all possible pairs of turing machines and inputs, then we can let $S$ denote the set of those positive integers $n$ for which the $n$th pair halts. Now this number $x$ will be well-defined but uncomputable:

$$x = \frac 1 3 + 4\sum_{n \in S} 10^{-n}$$

$x$ will consist of a sequence of decimals all of which are either 3 or 7. The $n$th decimal will be 7 if the $n$th pair of turing machine and input halts, and 3 otherwise. In other words computing a decimal of $x$ is equivalent to solving an instance of the halting problem.

What is also interesting about $x$ is that there is a simple constructive algorithm to produce a sequence of rational numbers, that converge towards $x$.

  • Initialize $a := \frac 1 3$
  • For $i \in \mathbb{N}$ do:
    • Simulate the first $i$ turing machines for the first $i$ steps.
    • For each turing machine $n$ which halted and did not halt for any lower $i$:
      • $a := a + 4 \cdot 10 ^{-n}$
      • Output $a$

This shows that it possible for a computable sequence of rational numbers to converge on a non-computable number. This is a bit more than what you asked for, but to me this particular example gave me a better feeling for what the boundary of compatibility looks like.

$\endgroup$
  • $\begingroup$ How is this more than what was asked? The rational numbers are dense in $\Bbb R$. So if there is an uncomputable real, there is a sequence of rationals converging to it. $\endgroup$ – Asaf Karagila May 5 '15 at 4:14
  • $\begingroup$ @AsafKaragila Because in this case the sequence is computable. Every number in $\mathbb{R}$ will be the limit of a sequence of rational numbers, but for most of them the sequence will not be computable. $\endgroup$ – kasperd May 5 '15 at 5:13
  • $\begingroup$ @AsafKaragila: He means that there is a Turing machine that outputs a sequence of Turing machines that all halt and whose output converges to the uncomputable real number. There just isn't a Turing machine that outputs the sequence of digits of that real number. The crucial difference is that the sequence converges at an uncomputable rate but outputting the digits in order requires a linear convergence. kasperd, you might want to include such kinds of detail in your answer to make it more complete. =) $\endgroup$ – user21820 May 5 '15 at 12:17
2
$\begingroup$

The simplest is perhaps the uncomputable real number whose binary expansion is $$0.x_1x_2x_3...$$ where $$x_i = \begin{cases} 1 & \text{if }T_i\text{ eventually halts}\\ 0 & \text{otherwise} \end{cases} $$ and $T_i$ is the $i$th Turing machine (in some chosen ordering) with an initially blank tape.

$\endgroup$
-1
$\begingroup$

$\Sigma(1000)$ where $\Sigma$ is the Busy Beaver function.

Edit: A better example is Chaitin's constant.

$\endgroup$
  • 1
    $\begingroup$ How do you figure it isn't computable? $\endgroup$ – Asaf Karagila May 4 '15 at 15:48
  • 6
    $\begingroup$ Every integer is computable. You just can't prove it's $\Sigma(1000)$. $\endgroup$ – Matt Samuel May 4 '15 at 15:49
  • 10
    $\begingroup$ $\Sigma$ is not a computable function. However given any integer there is a computer program that will output it. Namely you can just add $1$ that many times to 0 then print the result. $\endgroup$ – Matt Samuel May 4 '15 at 15:50
  • 4
    $\begingroup$ More generally, any real number with finitely many nonzero digits is computable. $\endgroup$ – Matt Samuel May 4 '15 at 15:52
  • 3
    $\begingroup$ @MattSamuel Even more generally, every algebraic number (which includes every rational number) is computable. $\endgroup$ – Jeppe Stig Nielsen May 5 '15 at 10:42

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.