7 ms·

I'm not making much sense of that article. It's rejecting both the mathematical definition of continuity, and also wants to compute with infinite real numbers,

I'm not making much sense of that article. It's rejecting both the mathematical definition of continuity, and also wants to compute with infinite real numbers, which is just not realistic to computers and languages. So the author ends up with a lot of absurd results.

throwawaymath 7y ago
That's because the author is using constructive mathematics (i.e. computable analysis instead of standard real analysis). It is true that all computable functions are continuous. Likewise discontinuous real functions aren't computable. The continuum hypothesis is tangentially related to this topic and makes for fun reading.
- alain94040 7y ago
  But this is begging the question. The author uses the definition that numbers have infinite decimals, and all you are allowed to do is ask for decimal n to find out a number. You can never grasp the full number, since you are given a finite amount of time (compute) to discover an infinite sequence of decimals. From that definition, it's quite obvious that everything you compute has to be continuous, because you are never sure of what other decimals may be coming up, so whatever you compute has to be close enough. That sounds more like an argument that representing numbers that way is not particularly useful since you can't do much with them (you can't even provide an equality operator).
  - edflsafoiewq 7y ago
    A constructive response is that the ability to examine a real number to arbitrary precision is already highly idealized. In the real world you will quickly exhaust your ability to measure a real quantity to ever higher precision. > you can't even provide an equality operator If you are given two rods, there is no way to tell if the two rods are of the same length.
  - throwawaymath 7y ago
    I'm not sure I'm following you. I'm also not arguing for or against the results here. I'm just giving you the background to understand the author's point; it's not something they just came up with, it's been under study for quite a while in constructivist mathematics. I also don't really think you're using the right definition of computable here. You make it sound as though we're estimating, or truncating uncomputable numbers to make them computable when you say: > From that definition, it's quite obvious that everything you compute has to be continuous, because you are never sure of what other decimals may be coming up, so whatever you compute has to be close enough. It's not about being close enough or estimating, they're categorically different things. You can't obtain an uncomputable number, even by estimating, to any meaningful precision with a finite amount of time. So what are you saying here?
- jayd16 7y ago
  >In fact, no finite amount of computation will guarantee that we will be able to tell whether x=0 or x>0 Hmm, I'm still stuck at this assertion. Why can we not assume the number is finite? If we assume an infinitely long number takes an infinite amount of time to read, can we not also assume it must take an infinite amount of time to write? If we only have finite time, can we not assume all numbers given to the function in that time are finite?
  - danharaj 7y ago
    A program that takes an integer n and outputs the n'th digit of the number it represents is a finite representation of an infinite stream of digits.
  - afc 7y ago
    Yeah, I'm also stuck here. The article seems to say that, because you can't produce an upper bound to the amount of time the sgn function will take to run (for all possible inputs), sgn isn't a function. But then... isn't it the same for every single other function? I think the article is conflating "given a fixed amount of time, one can find an input for which the function will take longer to run" with "the function takes infinite time". The later isn't true: for any given input, no matter how big, one can compute a time such that the function will finish in that time; in other words, the function always finishes, in finite time, for every possible input, no matter how large. It's possible we're both confused, I suppose. :-)
    - Ericson2314 7y ago
      Here's the thing: the "discrete vs continuous" most people were taught is wrong. Discrete is [can always be construed as] continuous. Only infinite things can be discontinuous. State is finite but time is countably infinite for our purposes, so we model infinite/unbounded things with programs that can run arbitrary long. Finally, this abstract math stuff is in fact a really good UI point that most programmers miss. In non "real time" applications, you should aim to be able to dynamically tradeoff tardiness and richness; e.g. a fancy diagram that is rendered at low res and then higher res. Likewise all your caches should be evictable under memory pressure. Computing should feel fluid. It's a pity most people only paleolithic state machine math or terminating thing math. This falsely implies that "real world programs" which hardly ever terminate are beyond theory, or that the smartypants thing to do is break them down into little terminating programs and some big spooky event loop whateverthefuck (browser, apache, framework du jour, etc etc.). Build codata out of codata!
edflsafoiewq 7y ago
You may like the whole list of constructive gems and stones then: http://math.andrej.com/category/gems-and-stones/ http://math.andrej.com/category/gems-and-stones/ :) As a sampler, the following are all constructively false (ie. imply the law of excluded middle) * Every finite set can be enumerated without repetitions * A subset of a finite set is finite * The intersection of finite sets is finite
- lonelappde 7y ago
  Note that these results rely on a technical definition of set that is rather abstract mathematically, in a way programers may find amusing. It defines a set as a potentially infinite list with potential duplicates, from which we can observe that some lists cannot be deduplicated in finite time, making certain operations that are easy on computer science sets not always possible on computer science lists. For example, is A a subset of B={0}, if all you know about A is that it is a Java iteratable that returns 0 for the first 10^3000 elements you examine?
blablabla123 7y ago
It's a bit unclear, also the conclusion. However most definitions of continuity are just covering real functions. I remember my math prof stating that there are also continuous functions on the natural numbers (N->N), IIRC n -> n^2 would be an example. Given that numerical calculations are not on R - at best on Q - this doesn't sound so far-fetched
lonelappde 7y ago
The results are only absurd if you hold absurd axioms like believing that uncomputable numbers can be computed, or that the real number set is real.

throwawaymath 7y ago

That's because the author is using constructive mathematics (i.e. computable analysis instead of standard real analysis). It is true that all computable functions are continuous. Likewise discontinuous real functions aren't computable. The continuum hypothesis is tangentially related to this topic and makes for fun reading.

alain94040 7y ago
But this is begging the question. The author uses the definition that numbers have infinite decimals, and all you are allowed to do is ask for decimal n to find out a number. You can never grasp the full number, since you are given a finite amount of time (compute) to discover an infinite sequence of decimals. From that definition, it's quite obvious that everything you compute has to be continuous, because you are never sure of what other decimals may be coming up, so whatever you compute has to be close enough. That sounds more like an argument that representing numbers that way is not particularly useful since you can't do much with them (you can't even provide an equality operator).
- edflsafoiewq 7y ago
  A constructive response is that the ability to examine a real number to arbitrary precision is already highly idealized. In the real world you will quickly exhaust your ability to measure a real quantity to ever higher precision. > you can't even provide an equality operator If you are given two rods, there is no way to tell if the two rods are of the same length.
- throwawaymath 7y ago
  I'm not sure I'm following you. I'm also not arguing for or against the results here. I'm just giving you the background to understand the author's point; it's not something they just came up with, it's been under study for quite a while in constructivist mathematics. I also don't really think you're using the right definition of computable here. You make it sound as though we're estimating, or truncating uncomputable numbers to make them computable when you say: > From that definition, it's quite obvious that everything you compute has to be continuous, because you are never sure of what other decimals may be coming up, so whatever you compute has to be close enough. It's not about being close enough or estimating, they're categorically different things. You can't obtain an uncomputable number, even by estimating, to any meaningful precision with a finite amount of time. So what are you saying here?
jayd16 7y ago
>In fact, no finite amount of computation will guarantee that we will be able to tell whether x=0 or x>0 Hmm, I'm still stuck at this assertion. Why can we not assume the number is finite? If we assume an infinitely long number takes an infinite amount of time to read, can we not also assume it must take an infinite amount of time to write? If we only have finite time, can we not assume all numbers given to the function in that time are finite?
- danharaj 7y ago
  A program that takes an integer n and outputs the n'th digit of the number it represents is a finite representation of an infinite stream of digits.
- afc 7y ago
  Yeah, I'm also stuck here. The article seems to say that, because you can't produce an upper bound to the amount of time the sgn function will take to run (for all possible inputs), sgn isn't a function. But then... isn't it the same for every single other function? I think the article is conflating "given a fixed amount of time, one can find an input for which the function will take longer to run" with "the function takes infinite time". The later isn't true: for any given input, no matter how big, one can compute a time such that the function will finish in that time; in other words, the function always finishes, in finite time, for every possible input, no matter how large. It's possible we're both confused, I suppose. :-)
  - Ericson2314 7y ago
    Here's the thing: the "discrete vs continuous" most people were taught is wrong. Discrete is [can always be construed as] continuous. Only infinite things can be discontinuous. State is finite but time is countably infinite for our purposes, so we model infinite/unbounded things with programs that can run arbitrary long. Finally, this abstract math stuff is in fact a really good UI point that most programmers miss. In non "real time" applications, you should aim to be able to dynamically tradeoff tardiness and richness; e.g. a fancy diagram that is rendered at low res and then higher res. Likewise all your caches should be evictable under memory pressure. Computing should feel fluid. It's a pity most people only paleolithic state machine math or terminating thing math. This falsely implies that "real world programs" which hardly ever terminate are beyond theory, or that the smartypants thing to do is break them down into little terminating programs and some big spooky event loop whateverthefuck (browser, apache, framework du jour, etc etc.). Build codata out of codata!

edflsafoiewq 7y ago

You may like the whole list of constructive gems and stones then: http://math.andrej.com/category/gems-and-stones/ http://math.andrej.com/category/gems-and-stones/ :) As a sampler, the following are all constructively false (ie. imply the law of excluded middle) * Every finite set can be enumerated without repetitions * A subset of a finite set is finite * The intersection of finite sets is finite

lonelappde 7y ago
Note that these results rely on a technical definition of set that is rather abstract mathematically, in a way programers may find amusing. It defines a set as a potentially infinite list with potential duplicates, from which we can observe that some lists cannot be deduplicated in finite time, making certain operations that are easy on computer science sets not always possible on computer science lists. For example, is A a subset of B={0}, if all you know about A is that it is a Java iteratable that returns 0 for the first 10^3000 elements you examine?

blablabla123 7y ago

It's a bit unclear, also the conclusion. However most definitions of continuity are just covering real functions. I remember my math prof stating that there are also continuous functions on the natural numbers (N->N), IIRC n -> n^2 would be an example. Given that numerical calculations are not on R - at best on Q - this doesn't sound so far-fetched

lonelappde 7y ago

The results are only absurd if you hold absurd axioms like believing that uncomputable numbers can be computed, or that the real number set is real.