6 ms·

>We can not obtain them to feed them as input, our real-world machines can not process them if we could... I'm not sure about this. We often make calculations

>We can not obtain them to feed them as input, our real-world machines can not process them if we could... I'm not sure about this. We often make calculations with computer representations of real numbers. We can calculate quantities based on algebraic or transcendental numbers with arbitrary precision (optimizations, navigation), or we can use them as a basis (image processing) and represent rational numbers in their terms. Real numbers are all over computer applications.

wyattpeak 8y ago
Arbitrary precision is irrelevant. By it we mean arbitrary finite precision, which leaves us not only with computable numbers, but rationals. Representing rationals isn't affected by the paper's findings, because they have the same cardinality as the naturals. Arbitrary precision models reals, it doesn't actually use them.
- mike00632 8y ago
  >We can not obtain them to feed them as input, our real-world machines can not process them if we could Suppose we are only working with rational multiples of Pi. Then we can ONLY have finite calculations of irrational numbers and it's impossible to have a finite calculation of a rational number (except for multiplication by 0). >Representing rationals isn't affected by the paper's findings, because they have the same cardinality as the naturals. The Natural numbers are still infinite which presents its own inherent difficulty. It's not as though countability lends itself better to programming.
  - roywiggins 8y ago
    All of the rationals are computable. Almost all of the irrationals aren't computable at all... so there's a big difference there.
    - mike00632 8y ago
      Yeah, and I suspect that has a lot to do with the underlying mathematical principles too. But the paper instead reduces the issue to the Continuum Hypothesis. The problem might not even have anything to do with countability but instead be fundamentally about the differences between infinite cardinals.
  - throwawaymath 8y ago
    First and foremost: > The Natural numbers are still infinite which presents its own inherent difficulty. It's not as though countability lends itself better to programming Actually countability does lend itself to programming, essentially by definition. You cannot write a function to enumerate all the real numbers precisely because they're uncountable, even if you had an infinite amount of time. You can trivially do this with a "merely" countably infinite set, like the naturals or rationals. > Suppose we are only working with rational multiples of Pi. Then we can ONLY have finite calculations of irrational numbers and it's impossible to have a finite calculation of a rational number (except for multiplication by 0). It sounds like you're suggesting we can store an irrational number in a finite representation by generating it with a finite function (e.g. multiply a rational number of times). But that doesn't work. You can't represent a number N in a finite number of steps if you can't represent all factors of N in a finite number of steps. This fact follows from the field axioms for the same reason that all products of irrationals and rationals are themselves irrational. Simply put, if you can't do it for Pi, you can't do it for a rational multiple of Pi.
    - mike00632 8y ago
      >You cannot write a function to enumerate all the real numbers precisely because they're uncountable, even if you had an infinite amount of time Even with infinite amount of time your enumeration function will not generate all of the natural numbers even though the natural number are countable. You're right that we can't write a function to determine an immediate successor but we can write successor functions. >It sounds like you're suggesting we can store an irrational number in a finite representation by generating it with a finite function (e.g. multiply a rational number of times). But that doesn't work. You can't represent a number N in a finite number of steps if you can't represent all factors of N in a finite number of steps. We are getting a few concepts muddled. Storing an irrational number as a finite representation is trivially easy. For example: "pi". Alternatively I could write an algorithm to generate the decimal expansion of the square root of 2. Where it's difficult is when we talk about numbers that aren't describable in a finite number of terms, i.e. Uncomputable. There is a certain unknowable quality to these numbers and I would suggest that this isn't inherent from the cardinality of the real numbers and that we run into similar problems when trying to compute some natural numbers, like random numbers.
  - lmm 8y ago
    > Suppose we are only working with rational multiples of Pi. How would you start? You can't put a rational multiple of pi exactly into a computer. You can't get a rational multiple of pi exactly out of a computer. You can calculate rational numbers on the computer and scale them by a factor of pi outside the computer, if you really want, but that doesn't mean the computer is working with irrationals. > It's not as though countability lends itself better to programming. Huh? Yes it does; countable sets are still infinite but they're better-behaved than bigger sets.
    - mike00632 8y ago
      >You can't put a rational multiple of pi exactly into a computer. Of course we can: "1/2*pi" >You can't get a rational multiple of pi exactly out of a computer. Using the same limitations you seem to have in mind, we can't get one third exactly either. >...countable sets are still infinite but they're better-behaved than bigger sets. Yes, and that is surprising because we do have numerous clever applications that skirt around most of the intractability of exotic real numbers. That is why I think this paper is a bid deal, especially because it points to the cardinality of the real numbers instead of, say, their inclusion of the uncomputable numbers.
      - lmm 8y ago
        > Using the same limitations you seem to have in mind, we can't get one third exactly either. We can work with exact rationals; we can do arithmetic on them and normalize them. In particular, we can compute whether two rationals are equal (in finite time), which we can't do with reals.
throwawaymath 8y ago
No, we often make calculations with a finite, countable subset of real numbers. We can only approximate the real numbers with finite precision.
- mike00632 8y ago
  >we often make calculations with a finite, countable subset of real numbers. We also often make calculations with finite subsets of rational numbers. We don't work with all of the rational numbers. > We can only approximate the real numbers with finite precision. The same can be said for rational numbers. It really matters that we can be arbitrarily precise when we talk about .333333... (one third), 1.41421... (square root of 2) or 3.14159... (pi) because we can be as exact as our calculations demand.
  - roywiggins 8y ago
    We can effectively calculate all of the rationals to arbitrary precision, but we can't do that with all of the reals. Most of the reals have no effective procedure to calculate their decimal expansion.
    - mike00632 8y ago
      Right, but we're getting away from illustrating the point of the paper, which isn't about number computability (interestingly) but about cardinality of sets. The intractability of this machine learning problem could have more to do with an absence of a successor function in the Real numbers than about the cardinality of uncomputable numbers. Or it could be a consequence of properties of differing infinite sets in general, like the difference between the Reals and the power set of the Reals. What I'm trying to get at is that we're not just talking about infinite decimal expansions.
  - throwawaymath 8y ago
    Two points: First, yes the rationals are already countable. But the reals are uncountable. You cannot write a function to generate all real numbers - not even if you allowed the function to run for an infinite amount of time. Second, most of the reals are individually uncomputable, which literally means no, we cannot calculate them to arbitrary precision (or any exact precision). Likewise we cannot just redefine the set of real numbers to be restricted to the set of computable reals. Analysis rapidly breaks down when you do so and it follows that the real field is no longer closed (by definition, and therefore no longer subject to the field axioms).
h0mEDw 8y ago
It's extremely counter intuitive what would happen if a computer system (a Turing machine) was operating symbolically on real numbers, not floating point numbers which have vastly different properties (for example, addition is not associative there although it is commutative). We can refer to constructive logic proofs in the real number theory. There's a ton of surprising facts there, to pick two: 1. For x and y you cannot prove that x<=y or x=>y 2. Every function is continuous Some hand-waving to see why 1. is a problem: given two numbers, x and y, as a lazily-computed infinite decimal expansion, the program that loops in parallel over the expansions and seeks the first difference (to determine which number is greater) will never terminate if x and y have identical expansions. See this submission from two months ago: https://news.ycombinator.com/item?id=18411935 https://news.ycombinator.com/item?id=18411935
- PurpleBoxDragon 8y ago
  Isn't it also possible for two numbers to have unequal expansions but still be equal? Take .3... * 3 vs 1. The first expands to .9... while the second expands to 1.0... but they are also equal.
  - h0mEDw 8y ago
    Yup, it is possible. That was just a hand wavy example to show where the issue is. Symbolic real numbers need not be represented as small programs/objects generating a sequence of digits. But all of those implementations/representations will fail to compare some numbers. Edit: for instance, you could imagine a representation (think object of a virtual class in c++) that gives you a fraction and a 1/2^n bound for error, where you can query the number for whatever n you see fit. Still, in some cases it's undecidable to determine which number is greater.
  - mike00632 8y ago
    Right, but note that we can use numbers from countable sets and find different symbolic representations for them (3.0 vs 3). That problem is not inherent from the uncountability of the real numbers.
- mike00632 8y ago

wyattpeak 8y ago

Arbitrary precision is irrelevant. By it we mean arbitrary finite precision, which leaves us not only with computable numbers, but rationals. Representing rationals isn't affected by the paper's findings, because they have the same cardinality as the naturals. Arbitrary precision models reals, it doesn't actually use them.

mike00632 8y ago
>We can not obtain them to feed them as input, our real-world machines can not process them if we could Suppose we are only working with rational multiples of Pi. Then we can ONLY have finite calculations of irrational numbers and it's impossible to have a finite calculation of a rational number (except for multiplication by 0). >Representing rationals isn't affected by the paper's findings, because they have the same cardinality as the naturals. The Natural numbers are still infinite which presents its own inherent difficulty. It's not as though countability lends itself better to programming.
- roywiggins 8y ago
  All of the rationals are computable. Almost all of the irrationals aren't computable at all... so there's a big difference there.
  - mike00632 8y ago
    Yeah, and I suspect that has a lot to do with the underlying mathematical principles too. But the paper instead reduces the issue to the Continuum Hypothesis. The problem might not even have anything to do with countability but instead be fundamentally about the differences between infinite cardinals.
- throwawaymath 8y ago
  First and foremost: > The Natural numbers are still infinite which presents its own inherent difficulty. It's not as though countability lends itself better to programming Actually countability does lend itself to programming, essentially by definition. You cannot write a function to enumerate all the real numbers precisely because they're uncountable, even if you had an infinite amount of time. You can trivially do this with a "merely" countably infinite set, like the naturals or rationals. > Suppose we are only working with rational multiples of Pi. Then we can ONLY have finite calculations of irrational numbers and it's impossible to have a finite calculation of a rational number (except for multiplication by 0). It sounds like you're suggesting we can store an irrational number in a finite representation by generating it with a finite function (e.g. multiply a rational number of times). But that doesn't work. You can't represent a number N in a finite number of steps if you can't represent all factors of N in a finite number of steps. This fact follows from the field axioms for the same reason that all products of irrationals and rationals are themselves irrational. Simply put, if you can't do it for Pi, you can't do it for a rational multiple of Pi.
  - mike00632 8y ago
    >You cannot write a function to enumerate all the real numbers precisely because they're uncountable, even if you had an infinite amount of time Even with infinite amount of time your enumeration function will not generate all of the natural numbers even though the natural number are countable. You're right that we can't write a function to determine an immediate successor but we can write successor functions. >It sounds like you're suggesting we can store an irrational number in a finite representation by generating it with a finite function (e.g. multiply a rational number of times). But that doesn't work. You can't represent a number N in a finite number of steps if you can't represent all factors of N in a finite number of steps. We are getting a few concepts muddled. Storing an irrational number as a finite representation is trivially easy. For example: "pi". Alternatively I could write an algorithm to generate the decimal expansion of the square root of 2. Where it's difficult is when we talk about numbers that aren't describable in a finite number of terms, i.e. Uncomputable. There is a certain unknowable quality to these numbers and I would suggest that this isn't inherent from the cardinality of the real numbers and that we run into similar problems when trying to compute some natural numbers, like random numbers.
- lmm 8y ago
  > Suppose we are only working with rational multiples of Pi. How would you start? You can't put a rational multiple of pi exactly into a computer. You can't get a rational multiple of pi exactly out of a computer. You can calculate rational numbers on the computer and scale them by a factor of pi outside the computer, if you really want, but that doesn't mean the computer is working with irrationals. > It's not as though countability lends itself better to programming. Huh? Yes it does; countable sets are still infinite but they're better-behaved than bigger sets.
  - mike00632 8y ago
    >You can't put a rational multiple of pi exactly into a computer. Of course we can: "1/2*pi" >You can't get a rational multiple of pi exactly out of a computer. Using the same limitations you seem to have in mind, we can't get one third exactly either. >...countable sets are still infinite but they're better-behaved than bigger sets. Yes, and that is surprising because we do have numerous clever applications that skirt around most of the intractability of exotic real numbers. That is why I think this paper is a bid deal, especially because it points to the cardinality of the real numbers instead of, say, their inclusion of the uncomputable numbers.
    - lmm 8y ago
      > Using the same limitations you seem to have in mind, we can't get one third exactly either. We can work with exact rationals; we can do arithmetic on them and normalize them. In particular, we can compute whether two rationals are equal (in finite time), which we can't do with reals.

throwawaymath 8y ago

No, we often make calculations with a finite, countable subset of real numbers. We can only approximate the real numbers with finite precision.

mike00632 8y ago
>we often make calculations with a finite, countable subset of real numbers. We also often make calculations with finite subsets of rational numbers. We don't work with all of the rational numbers. > We can only approximate the real numbers with finite precision. The same can be said for rational numbers. It really matters that we can be arbitrarily precise when we talk about .333333... (one third), 1.41421... (square root of 2) or 3.14159... (pi) because we can be as exact as our calculations demand.
- roywiggins 8y ago
  We can effectively calculate all of the rationals to arbitrary precision, but we can't do that with all of the reals. Most of the reals have no effective procedure to calculate their decimal expansion.
  - mike00632 8y ago
    Right, but we're getting away from illustrating the point of the paper, which isn't about number computability (interestingly) but about cardinality of sets. The intractability of this machine learning problem could have more to do with an absence of a successor function in the Real numbers than about the cardinality of uncomputable numbers. Or it could be a consequence of properties of differing infinite sets in general, like the difference between the Reals and the power set of the Reals. What I'm trying to get at is that we're not just talking about infinite decimal expansions.
- throwawaymath 8y ago
  Two points: First, yes the rationals are already countable. But the reals are uncountable. You cannot write a function to generate all real numbers - not even if you allowed the function to run for an infinite amount of time. Second, most of the reals are individually uncomputable, which literally means no, we cannot calculate them to arbitrary precision (or any exact precision). Likewise we cannot just redefine the set of real numbers to be restricted to the set of computable reals. Analysis rapidly breaks down when you do so and it follows that the real field is no longer closed (by definition, and therefore no longer subject to the field axioms).

h0mEDw 8y ago

It's extremely counter intuitive what would happen if a computer system (a Turing machine) was operating symbolically on real numbers, not floating point numbers which have vastly different properties (for example, addition is not associative there although it is commutative). We can refer to constructive logic proofs in the real number theory. There's a ton of surprising facts there, to pick two: 1. For x and y you cannot prove that x<=y or x=>y 2. Every function is continuous Some hand-waving to see why 1. is a problem: given two numbers, x and y, as a lazily-computed infinite decimal expansion, the program that loops in parallel over the expansions and seeks the first difference (to determine which number is greater) will never terminate if x and y have identical expansions. See this submission from two months ago: https://news.ycombinator.com/item?id=18411935 https://news.ycombinator.com/item?id=18411935

PurpleBoxDragon 8y ago
Isn't it also possible for two numbers to have unequal expansions but still be equal? Take .3... * 3 vs 1. The first expands to .9... while the second expands to 1.0... but they are also equal.
- h0mEDw 8y ago
  Yup, it is possible. That was just a hand wavy example to show where the issue is. Symbolic real numbers need not be represented as small programs/objects generating a sequence of digits. But all of those implementations/representations will fail to compare some numbers. Edit: for instance, you could imagine a representation (think object of a virtual class in c++) that gives you a fraction and a 1/2^n bound for error, where you can query the number for whatever n you see fit. Still, in some cases it's undecidable to determine which number is greater.
- mike00632 8y ago
  Right, but note that we can use numbers from countable sets and find different symbolic representations for them (3.0 vs 3). That problem is not inherent from the uncountability of the real numbers.
mike00632 8y ago