3 ms·

> And almost all numbers cannot be expressed in IEEE floating points. It is a bit stronger than that. Almost all numbers cannot be practically expressed and it

by roenxi 2y ago

> And almost all numbers cannot be expressed in IEEE floating points. It is a bit stronger than that. Almost all numbers cannot be practically expressed and it may even be that the probability of a random number being theoretically indescribable is about 100%. Depending on what a number is. > Some problems can be avoided if you use bignums. Or that. My momentary existential angst has been assuaged. Thanks bignums.

mananaysiempre 2y ago
> 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
leereeves 2y ago
> Almost all numbers cannot be practically expressed That's certainly true, but all numbers that can be entered on a calculator can be expressed (for example, by the button sequence entered in the calculator). The calculator app can't help with the numbers that can't be practically expressed, it just needs to accurately approximate the ones that can.
- tialaramex 2y ago
  This behaviour is what you get in say a cheap 1980s digital calculator, but it's not what we actually want. We want correct answers and to do that you need to be smarter. Ideally impossibly smart, but if the calculator is smarter than the person operating it that's a good start. You're correct that the use of the calculator means we're talking about computable numbers, so that's nice - almost all Reals are non-computable but we ruled those out because we're using a calculator. However just because our results are Computable doesn't let us off the hook. There's a difference between knowing the answer is exactly 40 and knowing only that you've computed a few hundred decimal places after 40 and so far they're all zero, maybe the next one won't be.
  - kqr 2y ago
    > There's a difference between knowing the answer is exactly 40 and knowing only that you've computed a few hundred decimal places after 40 and so far they're all zero, maybe the next one won't be. I would guess that if you pulled in a random sample of 2000 users of pocket calculators and surveyed their use cases you would find a grand total of 0 of them in which the cost function evaluated on a hundredth-decimal place error is at all meaningful. In other words, no, that difference is not meaningful to a user of a pocket calculator.
    - lupire 2y ago
      What don't seriously curious people deserve pocket calculators?
      - Dylan16807 2y ago
GMoromisato 2y ago
Does it matter that some numbers are inexpressible (i.e., cannot be computed)? I don't think it matters on a practical level--it's not like the cure for cancer is embedded in an inexpressible number (because the cure to cancer has to be a computable number, otherwise, we couldn't actually cure cancer). But does it matter from a theoretical/math perspective? Are there some theorems or proofs that we cannot access because of inexpressible numbers? [Forgive my ignorance--I'm just a dumb programmer.]
- lupire 2y ago
  It doesn't "matter", but it's interesting to probe the boundary between the easily accessible world and the probably inaccessible world. Non-discrete real-number-based Fractals are a beautiful visual version of this.
- yen223 2y ago
  We know of at least one uncomputable number - Chaitin's constant, the probability that any given Turing machine halts. Personally, I do wonder sometimes if real-world physical processes can involve uncomputable numbers. Can an object be placed X units away from some point, where X is an uncomputable number? The implications would be really interesting, no matter whether the answer is yes or no.
- kccqzy 2y ago
  Well some classical techniques in standard undergraduate real analysis could lead to numbers outside the set of computable numbers, so if you don't allow non-computable numbers you will need to be more careful in the theorems you derive in real analysis. I do not believe that is important however; it's much simpler to just work with the set of real numbers rather than the set of computable numbers.
ChadNauseam 2y ago
I worded that sentence carefully, when I said “almost all” :)
rocqua 2y ago
> Almost all numbers cannot be practically expressed and it may even be that the probability of a random number being theoretically indescribable is about 100%. Depending on what a number is. A common rebuke is that the construction of the 'real numbers' is so overwrought that most of them have no real claim to 'existing' at all.

by roenxi 2y ago

mananaysiempre 2y ago

> 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

leereeves 2y ago

> Almost all numbers cannot be practically expressed That's certainly true, but all numbers that can be entered on a calculator can be expressed (for example, by the button sequence entered in the calculator). The calculator app can't help with the numbers that can't be practically expressed, it just needs to accurately approximate the ones that can.

tialaramex 2y ago
This behaviour is what you get in say a cheap 1980s digital calculator, but it's not what we actually want. We want correct answers and to do that you need to be smarter. Ideally impossibly smart, but if the calculator is smarter than the person operating it that's a good start. You're correct that the use of the calculator means we're talking about computable numbers, so that's nice - almost all Reals are non-computable but we ruled those out because we're using a calculator. However just because our results are Computable doesn't let us off the hook. There's a difference between knowing the answer is exactly 40 and knowing only that you've computed a few hundred decimal places after 40 and so far they're all zero, maybe the next one won't be.
- kqr 2y ago
  > There's a difference between knowing the answer is exactly 40 and knowing only that you've computed a few hundred decimal places after 40 and so far they're all zero, maybe the next one won't be. I would guess that if you pulled in a random sample of 2000 users of pocket calculators and surveyed their use cases you would find a grand total of 0 of them in which the cost function evaluated on a hundredth-decimal place error is at all meaningful. In other words, no, that difference is not meaningful to a user of a pocket calculator.
  - lupire 2y ago
    What don't seriously curious people deserve pocket calculators?
    - Dylan16807 2y ago

GMoromisato 2y ago

Does it matter that some numbers are inexpressible (i.e., cannot be computed)? I don't think it matters on a practical level--it's not like the cure for cancer is embedded in an inexpressible number (because the cure to cancer has to be a computable number, otherwise, we couldn't actually cure cancer). But does it matter from a theoretical/math perspective? Are there some theorems or proofs that we cannot access because of inexpressible numbers? [Forgive my ignorance--I'm just a dumb programmer.]

lupire 2y ago
It doesn't "matter", but it's interesting to probe the boundary between the easily accessible world and the probably inaccessible world. Non-discrete real-number-based Fractals are a beautiful visual version of this.
yen223 2y ago
We know of at least one uncomputable number - Chaitin's constant, the probability that any given Turing machine halts. Personally, I do wonder sometimes if real-world physical processes can involve uncomputable numbers. Can an object be placed X units away from some point, where X is an uncomputable number? The implications would be really interesting, no matter whether the answer is yes or no.
kccqzy 2y ago
Well some classical techniques in standard undergraduate real analysis could lead to numbers outside the set of computable numbers, so if you don't allow non-computable numbers you will need to be more careful in the theorems you derive in real analysis. I do not believe that is important however; it's much simpler to just work with the set of real numbers rather than the set of computable numbers.

ChadNauseam 2y ago

I worded that sentence carefully, when I said “almost all” :)

rocqua 2y ago

> Almost all numbers cannot be practically expressed and it may even be that the probability of a random number being theoretically indescribable is about 100%. Depending on what a number is. A common rebuke is that the construction of the 'real numbers' is so overwrought that most of them have no real claim to 'existing' at all.