Real numbers



${\mathbb R}$


axiomatics and cardinality
Specker sequence

Choose a programming language and index all Turing machines (or executable program) by $i$.

Let $h(i,s)$ be $0$ or $1$, depending on whether the machine with index $i$ halts before $s$ steps. For any given pair of numbers, you can indeed compute $h(i,s)$ by just running the program and wait $s$ time steps.

Define a sequence of rationals by having the $n$'th number given by the following sum (where you run through i and run it to step $ s=n-i $)

$a_n = \sum_{i+s=n} \dfrac {h(i,s)} {2^i} $

This is some number between 0 and 1.

But computing limit n to infinity (and thus s to infinity for all i) requires knowledge whether Turing machines ever halt, which we know to be impossible since the 30's. Thus this real number is not computable.

And most real numbers are worse, really, because this number is at least definable. Most reals aren't even that.


Link to graph
Log In
Improvements of the human condition