Differences
This shows you the differences between two versions of the page.
Both sides previous revision Previous revision | Next revision Both sides next revision | ||
real_numbers [2014/12/27 19:32] nikolaj |
real_numbers [2016/01/19 22:18] nikolaj |
||
---|---|---|---|
Line 9: | Line 9: | ||
=== Discussion === | === Discussion === | ||
>axiomatics and cardinality | >axiomatics and cardinality | ||
+ | |||
+ | == Specker sequence == | ||
+ | |||
+ | >>7793253 | ||
+ | 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} \frac {1} {2^i} h(i,s)$ | ||
+ | |||
+ | 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. | ||
=== References === | === References === |