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
real_numbers [2014/12/27 19:32]
nikolaj
real_numbers [2016/01/19 22:18] (current)
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} \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.
  
 === References === === References ===
Link to graph
Log In
Improvements of the human condition