3 ms·
For all real numbers in bulk— You may call it a diagonal argument, but it’s just a reduction to Cantor’s original statement, no new proof needed. There are only
by mananaysiempre 2y ago
For all real numbers in bulk— You may call it a diagonal argument, but it’s just a reduction to Cantor’s original statement, no new proof needed. There are only countably many computable numbers, because there are only countably many programs, because there are only countably many finite strings over any finite alphabet[1].
For individual real numbers— There are of course provably uncomputable ones. Chaitin’s constant is the poster child of these, but you could just take a map of (number of Turing machine in any numbering of all of them) to (terminates or not) and call that a binary fraction. (This is actually not far away from Chaitin’s constant, but the actual one is reweighted a bit to make it more meaningful.) Are there unprovably uncomputable ones? At a guess I’d say so, but I’m not good enough to give a construction offhand.
[1] A countable union of (finite or) countable sets is finite. Rahzrengr gur havba nf sbyybjf: svefg vgrz bs svefg frg; frpbaq vgrz bs svefg frg, svefg vgrz bs frpbaq frg; guveq vgrz bs svefg frg, frpbaq vgrz bs frpbaq frg, svefg vgrz bs guveq frg; rgp. Vg’f snveyl boivbhf gung guvf jbexf, ohg vs lbh jnag gb jevgr gur vairefr znccvat rkcyvpvgyl lbh pna qenj guvf nf n yvar guebhtu gur vagrtre cbvagf bs n dhnqenag.
- Tainnor 2y ago> Rahzrengr gur havba nf sbyybjf: svefg vgrz bs svefg frg; frpbaq vgrz bs svefg frg, svefg vgrz bs frpbaq frg; guveq vgrz bs svefg frg, frpbaq vgrz bs frpbaq frg, svefg vgrz bs guveq frg; rgp. Vg’f snveyl boivbhf gung guvf jbexf, ohg vs lbh jnag gb jevgr gur vairefr znccvat rkcyvpvgyl lbh pna qenj guvf nf n yvar guebhtu gur vagrtre cbvagf bs n dhnqenag. You lost me here.
- defrost 2y agoTry: https://cryptii.com/pipes/rot13-decoder https://cryptii.com/pipes/rot13-decoder
- Tainnor 2y agoOk what was the point of that? It just needlessly degrades an otherwise informative post.
- defrost 2y agoYou're seriously asking _me_ what https://news.ycombinator.com/item?id=43068787 https://news.ycombinator.com/item?id=43068787 was thinking when they included a ROT-13 paragraph? Typically, since pre-WWW UseNet days it's been used as a standard "no-spoiler" technique so that those who don't want to see a movie twist, puzzle answer, etc don't accidently eyeball scan the give away. BTW, you're welcome, glad I could help.
- Tainnor 2y agoThanks for your help, I didn't mean to attack you.
- mananaysiempre 2y agoThe point is that, in my estimation, the statement in the footnote is a good exercise (provided that you don’t already know it, that it’s not immediately obvious to you, and that you’re still into set theory enough to know what countability and the diagonal argument are). I was initially tempted to just leave it as such, but then thought I’d provide the solution under a spoiler.
- Tainnor 2y agoThanks for clarifying. I'm not that young anymore, but I haven't seen this sort of spoiler tagging since forever (assuming that I ever saw it), so I just really didn't know what was going on. Maybe a simple reference to ROT13 at the beginning of your spoiler would have helped.
- mymoomin 2y agoYou have a typo in [1]. It should read "A countable union of (finite or) countable sets is countable."
- mananaysiempre 2y agoI do, thanks :)