4 ms·
Individual numbers can be uncomputable! For example, take your favorite enumeration of Turing machines, (T1, T2...) and write down a real number in binary wher
by boothby 1y ago
Individual numbers can be uncomputable! For example, take your favorite enumeration of Turing machines, (T1, T2...) and write down a real number in binary where the first bit is 0 if T1 halts and 1 otherwise, second bit is 0 if T2 halts... clearly this number is real and between 0 and 1, but it cannot be computed in finite time.
- Vecr 1y agoIf it had a finite size it would be computable.
- drdeca 1y agoPardon, I meant natural number. I should have specified.
- Scarblac 1y agoThat's a number in R, obviously most of them are uncomputable (there is a countable number of Turing machines). But for every natural number n there is a trivial Turing machine that just prints n and then halts.