6 ms·

> existential angst The best (and most educational) expression of that angst that I know: https://mathwithbaddrawings.com/2016/12/28/why-the-number-line-freaks

> existential angst The best (and most educational) expression of that angst that I know: https://mathwithbaddrawings.com/2016/12/28/why-the-number-line-freaks-me-out/ https://mathwithbaddrawings.com/2016/12/28/why-the-number-li....

roenxi 2y ago
Uncomputable! That was the word I wanted. I only remembered constructability but that was something else. Thanks.
TeMPOraL 2y ago
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?
- analog31 2y ago
  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."
- throw0000111 2y ago
  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.
- 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 ago
      Try: https://cryptii.com/pipes/rot13-decoder https://cryptii.com/pipes/rot13-decoder
      - Tainnor 2y ago
        Ok what was the point of that? It just needlessly degrades an otherwise informative post.
- School-Cotton 2y ago
  The proof of the existence of uncomputable numbers is very simple: there are countably many computer programs, but uncountably many numbers.
- GMoromisato 2y ago
  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.
ThrowawayR2 2y ago
SMBC manages to do it in a 4 panel comic: https://www.smbc-comics.com/comic/real-4 https://www.smbc-comics.com/comic/real-4

roenxi 2y ago

Uncomputable! That was the word I wanted. I only remembered constructability but that was something else. Thanks.

TeMPOraL 2y ago

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?

analog31 2y ago
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."
throw0000111 2y ago
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.
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 ago
    Try: https://cryptii.com/pipes/rot13-decoder https://cryptii.com/pipes/rot13-decoder
    - Tainnor 2y ago
      Ok what was the point of that? It just needlessly degrades an otherwise informative post.
School-Cotton 2y ago
The proof of the existence of uncomputable numbers is very simple: there are countably many computer programs, but uncountably many numbers.
GMoromisato 2y ago
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.

ThrowawayR2 2y ago

SMBC manages to do it in a 4 panel comic: https://www.smbc-comics.com/comic/real-4 https://www.smbc-comics.com/comic/real-4