Hacker Newsnew | past | comments | ask | show | jobs | submitlogin

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.


That'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.


Pardon, I meant natural number. I should have specified.


If it had a finite size it would be computable.




Guidelines | FAQ | Lists | API | Security | Legal | Apply to YC | Contact

Search: