Hacker News Reader

Comment by TeMPOraL | Hacker News Reader

Wait. Could we in principle find more ways to express some of those uncomputable numbers, or have we conclusively proven we just can't reach them - can't identify any of them in any way we could express?

EDIT: let me guess - there is a proof, and it's probably a flavor of the diagonal argument, right?

View on HN

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.

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

Try: https://cryptii.com/pipes/rot13-decoder

Ok what was the point of that? It just needlessly degrades an otherwise informative post.

You're seriously asking _me_ what 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.

Thanks for your help, I didn't mean to attack you.

The 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.

Thanks 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.

You have a typo in [1]. It should read "A countable union of (finite or) countable sets is countable."

I do, thanks :)

Yes there's a proof. One flavor is that in any system for expressing numbers using symbols, you can show a correspondence between finite strings of symbols, and whole numbers. So, what works for whole numbers also works for things like proofs and formulas. I think the correspondence may be called "Goedel numbering."

There are two ways to read that question.

If hypercomputation is possible, then there might be a way to express some of those uncomputable numbers. They just won't be possible with an ordinary Turing machine.

(If description is all you need, then it's already possible to describe some uncomputable numbers like Chaitin's constant. But you can't reliably list its digits on an ordinary computer.)

As for the other interpretation, "have we conclusively proven we can't reach them with an ordinary computer", IIRC, the proof that there are infinite uncomputable numbers is as follows: Consider a finitely large program that, when run, outputs the number in question. This program can be encoded as an integer - just read its (binary or source) bytes as a very large base-256 number. Since the set of possible programs is no larger than the set of integers, it's (at most) countably infinite. However, the real numbers are uncountably infinite. Thus a real number is almost never computable.

The proof of the existence of uncomputable numbers is very simple: there are countably many computer programs, but uncountably many numbers.

BTW: I tried constructing a new number that could not be computed by any other Turing machine using a variant of the diagonilization argument. Basically, enumerate all Turing machines that generate numbers:

Turing machine 1

Turing machine 2

Turing machine 3

...

Now construct a new Turing machine that produce a new number in which the first digit is the first digit of Turing machine 1, the second is the second digit of Turing machine 2, etc. Now add 1 (with wrap-around) to each digit.

This will generate a new number that cannot be generated by any of the existing Turing machines.

The bug with this argument (as ChatGPT pointed out) is that because of the halting problem, we cannot guarantee that any specific Turing machine will halt, so the constructed program will not halt, and thus cannot actually compute a number.

Reply on news.ycombinator.com