4 ms·

It goes a bit further than that even, it's not just sums of nth roots it's all formulae involving just sums, products and roots (basically any of the familiar a

It goes a bit further than that even, it's not just sums of nth roots it's all formulae involving just sums, products and roots (basically any of the familiar algebraic operations). This includes nested roots etc. Of course you can write them as a limit of such operations, but that's true for all numbers.

pfdietz 4y ago
If by "write them as a limit" you mean "give an algorithm for computing the i-th element of a sequence of rational numbers whose limit is the desired real number", then this is not true for almost all real numbers, since there are only a countable number of such algorithms.
- ogogmad 4y ago
  That's technically correct. But all real numbers in practice are computable.
  - pfdietz 4y ago
    I looked at your statement for a while and I can't figure out how it could be made to make any sense.
    - ogogmad 4y ago
      This might not be the best written or best sourced article, but I would start here: https://en.wikipedia.org/wiki/Computable_analysis https://en.wikipedia.org/wiki/Computable_analysis Most operations for defining real numbers are computable. The reason for this is that, in practice, continuous functions and functionals are the same thing as computable functions and functionals. Continuous functions which aren't computable are generally pathological curiosities. One consequence of this heuristic is that since the Riemann integral is a continuous functional, one might guess that it is also computable. Indeed it is (but the proof isn't obvious). This then implies the computability of the constant pi because pi is equal to the integral 1 ⌠ ⎮ ________ ⎮ ╱ 2 ⎮ 2⋅╲╱ 1 - x dx ⌡ -1 The computability of integration implies the computability of root-finding because one can use the argument principle to do it.
      - Someone 4y ago
        > Most operations for defining real numbers are computable. Isn’t that a tautology or at least selection bias? “Operation” seems to imply we can carry it out, which means the number can be computed. Even if we give “operation” a wider meaning to include those that can’t be carried out, are we deceiving ourselves that most of them are computable because most of those we have thought of in the history of mathematics are? Or do we really know something about the cardinalities of those sets?
      - pfdietz 4y ago
        And the total number of such definitions is countable (since each definition is a finite sequence of symbols from a finite alphabet). Therefore, the number of such definable real numbers is countable. Any real number will be arbitrarily close to a definable number (all rational numbers are definable in this sense) though.
  - hansvm 4y ago
    In domains like applied physics that's often true, but as programmers there are plenty of interesting questions we can't hope to answer in many real-world situations because of uncomputability: - Probability that a bit flip will introduce a bug - Number of reasonable ways to solve a problem in a given language for some measure of reasonableness (e.g., as a heuristic when examining whether two similar programs are similar out of necessity or if there might have been influence from one to the other or via some joint hidden variable) - (generally, most statistics over a space of programs) - Optimal super-optimization with jumps allowed - Minimal boilerplate complexity to describe an algorithm in a language - (generally, most questions about optimizing some target over a space of programs) - ...We don't care about all of them, but a vast array of questions about classes of programs are simply not answerable in any finite period of time. You might be able to answer the above for sufficiently small and well-behaved inputs (e.g., in restricted languages whose constraints enable certain sorts of static analyses), but in general you cannot, and it happens often enough to definitely be a problem for real-world programs.
- contravariant 4y ago
  Well, I didn't mean that, but sure. For what it's worth the numbers in question are computable.
  - cs137 4y ago
    Chaitin's constant (which is actually a family of constants, one that exists for each programming language) is not computable. It's the probability of a randomly generated program halting. One can imagine it being of interest, at least among theorists. That said, I struggle to think of other useful non-computable numbers, save contrived examples.

pfdietz 4y ago

If by "write them as a limit" you mean "give an algorithm for computing the i-th element of a sequence of rational numbers whose limit is the desired real number", then this is not true for almost all real numbers, since there are only a countable number of such algorithms.

ogogmad 4y ago
That's technically correct. But all real numbers in practice are computable.
- pfdietz 4y ago
  I looked at your statement for a while and I can't figure out how it could be made to make any sense.
  - ogogmad 4y ago
    This might not be the best written or best sourced article, but I would start here: https://en.wikipedia.org/wiki/Computable_analysis https://en.wikipedia.org/wiki/Computable_analysis Most operations for defining real numbers are computable. The reason for this is that, in practice, continuous functions and functionals are the same thing as computable functions and functionals. Continuous functions which aren't computable are generally pathological curiosities. One consequence of this heuristic is that since the Riemann integral is a continuous functional, one might guess that it is also computable. Indeed it is (but the proof isn't obvious). This then implies the computability of the constant pi because pi is equal to the integral 1 ⌠ ⎮ ________ ⎮ ╱ 2 ⎮ 2⋅╲╱ 1 - x dx ⌡ -1 The computability of integration implies the computability of root-finding because one can use the argument principle to do it.
    - Someone 4y ago
      > Most operations for defining real numbers are computable. Isn’t that a tautology or at least selection bias? “Operation” seems to imply we can carry it out, which means the number can be computed. Even if we give “operation” a wider meaning to include those that can’t be carried out, are we deceiving ourselves that most of them are computable because most of those we have thought of in the history of mathematics are? Or do we really know something about the cardinalities of those sets?
    - pfdietz 4y ago
      And the total number of such definitions is countable (since each definition is a finite sequence of symbols from a finite alphabet). Therefore, the number of such definable real numbers is countable. Any real number will be arbitrarily close to a definable number (all rational numbers are definable in this sense) though.
- hansvm 4y ago
  In domains like applied physics that's often true, but as programmers there are plenty of interesting questions we can't hope to answer in many real-world situations because of uncomputability: - Probability that a bit flip will introduce a bug - Number of reasonable ways to solve a problem in a given language for some measure of reasonableness (e.g., as a heuristic when examining whether two similar programs are similar out of necessity or if there might have been influence from one to the other or via some joint hidden variable) - (generally, most statistics over a space of programs) - Optimal super-optimization with jumps allowed - Minimal boilerplate complexity to describe an algorithm in a language - (generally, most questions about optimizing some target over a space of programs) - ...We don't care about all of them, but a vast array of questions about classes of programs are simply not answerable in any finite period of time. You might be able to answer the above for sufficiently small and well-behaved inputs (e.g., in restricted languages whose constraints enable certain sorts of static analyses), but in general you cannot, and it happens often enough to definitely be a problem for real-world programs.
contravariant 4y ago
Well, I didn't mean that, but sure. For what it's worth the numbers in question are computable.
- cs137 4y ago
  Chaitin's constant (which is actually a family of constants, one that exists for each programming language) is not computable. It's the probability of a randomly generated program halting. One can imagine it being of interest, at least among theorists. That said, I struggle to think of other useful non-computable numbers, save contrived examples.