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

The theorem(s) about uncomputable numbers do date back only as far as the 1940's, because that's when computability was first being discovered/invented. Yes, the point about there being uncountably many reals dates back to Cantor, but that's a different theorem, and a different proof. The existence of uncomputable numbers follows as a corollary from Cantor's first proof of 1874, but the conclusion must be drawn - it wasn't there in Cantor's work.

Specifically:

We can prove that there are uncomputable numbers simply by noting that the number of Turing machines is countable, so the number of computable numbers is countable. Since there are uncountably many reals (by Cantor - 1874) then we can conclude that there are numbers that cannot be produced by a Turing machine.



You're misunderstanding the theorem the author proved.

Theorem A (author's theorem): No mapping from finite-length strings to real numbers will hit all the real numbers.

Theorem B (your theorem): Let's map strings of finite length to real numbers as follows: Consider the string as the specification for a Turing machine. If the specification is syntactically OK as a Turing machine description, and the output is syntactically OK as the decimal expansion of a (potentially infinite) real number, then that string maps to that real number. Otherwise, the string maps to zero. Then this particular mapping doesn't hit all the real numbers.

It's obvious that Theorem B is just a special case of Theorem A. And it's also obvious that Theorem A is a trivial corollary of Cantor's result (that no mapping from natural numbers to real numbers hits all real numbers), with no Turing machines or computation theory anywhere in sight.

I can well believe that Theorem B was either proven by Turing himself, or established in the early years post-Turing; it's low-hanging fruit once you've defined Turing machines and are familiar with Cantor's results. And it could hardly have been proven before the Turing machines were defined! So Theorem B is a special case that could plausibly have first arisen in the 1940's, but Theorem A is actually the theorem the author is talking about.


You're right, although I wasn't so much misunderstanding, as misremembering. As so often happens, there's been a flurry of similar comments, and I mis-remembered what had been said, and hadn't re-read before commenting.

Apologies.




Consider applying for YC's Summer 2026 batch! Applications are open till May 4

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

Search: