Differences

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

 real_numbers [2014/12/27 19:32]nikolaj real_numbers [2016/01/19 22:18]nikolaj Both sides previous revision Previous revision 2016/01/19 22:18 nikolaj 2016/01/19 22:18 nikolaj 2016/01/19 22:18 nikolaj 2014/12/27 19:32 nikolaj 2014/12/27 19:30 nikolaj old revision restored (2014/12/27 19:12)2013/05/04 23:43 nikolaj removed2013/05/04 23:15 nikolaj created Next revision Previous revision 2016/01/19 22:18 nikolaj 2016/01/19 22:18 nikolaj 2016/01/19 22:18 nikolaj 2014/12/27 19:32 nikolaj 2014/12/27 19:30 nikolaj old revision restored (2014/12/27 19:12)2013/05/04 23:43 nikolaj removed2013/05/04 23:15 nikolaj created Last revision Both sides next revision 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 ===