Differences

This shows you the differences between two versions of the page.

Link to this comparison view

Both sides previous revision Previous revision
Next revision
Previous revision
Last 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 ==
 +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 ===
Link to graph
Log In
Improvements of the human condition