6 ms·

Sometimes all functions are continuous (2006)

60 points by lelf 7y ago

bordercases 7y ago
The article is a slow burn with a hilariously clickbait title but damn, those are some fascinating and significant consequences. > An interesting question comes to mind: which programming features, apart from the ones we mentioned above, allow us to program [computably continuous integer streams]? In terms of Haskell, the same question is which monads allow us to program [these streams]? > Can we do it without any extra features and use just “pure” functional programming? > If by pure functional programming we understand a functional programming language with natural numbers, booleans and recusive definitions, also known as PCF, the answer is no. The proof of this uses denotational semantics and domain theory, and I will not go into it now. You may entertain yourself by trying and failing to define [computably continuous integer streams] in pure Haskell or ML, i.e., no side effects, no exceptions, no mutable store, no parallelism, no monads. > ... The lesson is for those “experts” who “know” that all reasonable models of computation are equivalent to Turing machines. This is true if one looks just at functions from N to N. However, at higher types, such as the type of our function m, questions of representation become important, and it does matter which model of computation is used. It takes a hit on the trend that was in vogue in early 2010s to do AI and metaphysics on top of Kolmogorov Complexity, Solmonoff Induction, information physics... people took the Turing Equivalence as a carte blanche to say whatever willy-nilly thing you want about the (potentially) computable nature of reality without being informed by more naturalistic methods. This is harshed even further given that these information-theoretic arguments often used non-computable notions.
mturmon 7y ago
Note that the comments thread below the article addresses some of the natural objections to the novel results exhibited in the post.
- quotemstr 7y ago
  In particular, > the real number is not given by an infinite sequence that is actually written down anywhere, but rather as an algorithm, or a black box, which accepts a number n and outputs the n-th digit. At no point do I manipulate an infinite amount of information, yet I can look at any digit I want. Of course, I cannot look at all digits in a finite time, which is sort of the point of the post.
edflsafoiewq 7y ago
A related fact: all functions are defined on closed sets. You cannot "tell" whether a number is in a set or is a limit point of a set. Since all functions are continuous, they work at limit points too. As a "practical" consequence: the common design of a random() function returning values in [0, 1) is wrong. Any function you write cannot "tell" whether it got a 1 or not. These are still very good guidelines even for floating-point code, as long as you, like most everyone else, treat floats as a blackbox abstraction for "real" real numbers.
- poizan42 7y ago
  Well, random() functions that are normally used are defined on the [0, 1) interval of 32-bit or 64-bit IEEE 754 floating point numbers, for which it is very much computable to determine whether they are exactly 1 (there's nothing "real number" about them though, they all belong to a small finite subset of the rations). Of course that isn't really an open interval in the topological sense either.
  - edflsafoiewq 7y ago
    But that's why it's often a bad idea to test exact equality of floats: the equality test isn't continuous. In fact, for float computations it's usually even more important to use continuous (ie. error tolerant) functions, since floating-point operations can introduce errors.
    - saagarjha 7y ago
      Comparing IEEE 754 floating point number is well defined and computable because the domain is discontinuous. It’d be stupid to use anything else…
      - deleted 7y ago
        [deleted]
tel 7y ago
The punchline at the end is worth calling out: Turing Equivalence applies at first-order computations like `Nat -> Nat`, but fails at higher-order computation like `(Nat -> Nat) -> {0, 1}`.
alain94040 7y ago
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?
svat 7y ago
More precisely, all well-defined computable functions are continuous. For another exposition of the same (or similar) results, see also Dan Piponi's post from 2008 "What does topology have to do with computability?" at http://blog.sigfpe.com/2008/01/what-does-topology-have-to-do-with.html http://blog.sigfpe.com/2008/01/what-does-topology-have-to-do... Also, as a follow-up, you may be interested in Martin Escardo's 2007 post on the same blog: http://math.andrej.com/2007/09/28/seemingly-impossible-functional-programs/ http://math.andrej.com/2007/09/28/seemingly-impossible-funct...
carapace 7y ago
Greg Buchholz in the site's comments linked to Gregory Chaitin's "How real are real numbers?"[1] and asks, > Isn't it a little bit crazy to talk about computations on real numbers, when most of them are uncomputable/unnameable? [1] https://arxiv.org/pdf/math/0411418.pdf https://arxiv.org/pdf/math/0411418.pdf > Experimental physicists know how difficult accurate measurements are. No physical quantity has ever been measured with more than 15 or so digits of accuracy. Mathematicians, however, freely fantasize with infinite-precision real numbers. Nevertheless within pure math the notion of a real number is extremely problematic. We’ll compare and contrast two parallel historical episodes: > 1. the diagonal and probabilistic proofs that reals are uncountable, and > 2. the diagonal and probabilistic proofs that there are uncomputable reals. > Both case histories open chasms beneath the feet of mathematicians.
skybrian 7y ago
I'm not a mathematician, but it sounds like what this is saying is that as soon as you allow a number to contain an infinite number of digits, you can get an infinite loop when you try to do a simple comparison. (For example, try to compare pi to an number that's not-quite pi. It might be a little more or a little less, but you can't know this without looking at all the digits, which is impossible.) As a consequence, there are only two boolean-valued total functions: always return true, or always return false. I guess that's why we don't use infinite streams of numbers for computation.
- lonelappde 7y ago
  You don't need to look at all the digits, but there is no finite stopping point you can choose in advance. It's similar to the problem of comparing two natural numbers given in least significant bit order.
  - skybrian 7y ago
    Given a comparison function, an adversary can construct streams of digits that will make it run forever. This would be true either way. The problem seems to be with allowing algorithmically generated streams as input? Maybe our domain should be limited to numbers generated by algorithms that are known to terminate? But despite eliminating irrational numbers, this guarantee doesn't seem like enough for practical computing. Even arbitrary precision algorithms require their inputs not only to be computable, but actually computed in advance, showing at least that they fit in memory.
Nevermark 7y ago
I don't understand the point of arguments about constructible functions on unconstructable reals. I.e. reals with infinite digits and no finite symbolic representation. For anything actually computable (in finite time), on computable (in finite time) values, you will always get discrete (not continuous) functions on discrete (not continuous) values.
- vilhelm_s 7y ago
  The idea of computable reals go back to at least Turing. The idea is that a real number (or an operation on real numbers) is computable if we can compute the decimal digits, one by one. This way, if the user wants to know it to any desired precision, they just have to wait until the computer has printed that many decimals. You can equivalently treat them as terminating computable functions of type (nat -> bool), which computes the n:th binary decimal. This is actually a quite constructive notion! At least, it works well with intuinistic mathematics, which is why Andrej Bauer is writing about it.
  - Nevermark 7y ago
    Ok, that makes sense. Even when restricting numbers to reals with finite symbolic/program definition, comparing two such reals requires an unknown and unbounded number of their digits to be computed. If two symbolic representations define the same number, but it isn't obvious, a complete digit comparison will never end. Got it. Thank you!
mianos 7y ago
This reminds me of the coastline paradox: https://en.wikipedia.org/wiki/Coastline_paradox https://en.wikipedia.org/wiki/Coastline_paradox Specifically, due to the fractal nature of a coastline the length diverges to infinity. The theoretical length at the infinite scale is infinity.
improv32 7y ago
For a very nice into to constructive math, see this[0] link as well as some good HN discussion here[1]. [0]: https://home.sandiego.edu/~shulman/papers/rabbithole.pdf https://home.sandiego.edu/~shulman/papers/rabbithole.pdf [1]: https://news.ycombinator.com/item?id=18411935 https://news.ycombinator.com/item?id=18411935
Gehinnn 7y ago
How do you implement algorithms for real numbers if there uncountable many of them? There is always a real number your algorithm cannot read/process.
- lonelappde 7y ago
  Algorithms work fine on countable subsets of real numbers, as long as the set you use is discrete at some finite resolution. You only run into trouble if you have no lower bound for separation. It's the same problem even if you have only a countable number of numbers, but you have no lower bound for the smallest positive number or upper bound for the largest number. Even integers are non computable in finite time, one one of them might be arbitrarily large.
loicd 7y ago
The result presented in TFA is that all computable functions over the real numbers are continuous. To generalize that to 'all functions are continuous', you not only need to believe that all functions should be computable, which sounds reasonable for a constructivist, but also that all numbers should be real, which is not. Back when I was in academia, I remember a talk by a mathematician who thought that we should all be doing analysis with rational numbers rather than real numbers. With such a perspective, the sign function defined over rational numbers (e.g. presented as a pair numerator, denominator) is both discontinuous at 0 and computable.

60 points by lelf 7y ago

The article is a slow burn with a hilariously clickbait title but damn, those are some fascinating and significant consequences. > An interesting question comes to mind: which programming features, apart from the ones we mentioned above, allow us to program [computably continuous integer streams]? In terms of Haskell, the same question is which monads allow us to program [these streams]? > Can we do it without any extra features and use just “pure” functional programming? > If by pure functional programming we understand a functional programming language with natural numbers, booleans and recusive definitions, also known as PCF, the answer is no. The proof of this uses denotational semantics and domain theory, and I will not go into it now. You may entertain yourself by trying and failing to define [computably continuous integer streams] in pure Haskell or ML, i.e., no side effects, no exceptions, no mutable store, no parallelism, no monads. > ... The lesson is for those “experts” who “know” that all reasonable models of computation are equivalent to Turing machines. This is true if one looks just at functions from N to N. However, at higher types, such as the type of our function m, questions of representation become important, and it does matter which model of computation is used. It takes a hit on the trend that was in vogue in early 2010s to do AI and metaphysics on top of Kolmogorov Complexity, Solmonoff Induction, information physics... people took the Turing Equivalence as a carte blanche to say whatever willy-nilly thing you want about the (potentially) computable nature of reality without being informed by more naturalistic methods. This is harshed even further given that these information-theoretic arguments often used non-computable notions.

mturmon 7y ago

Note that the comments thread below the article addresses some of the natural objections to the novel results exhibited in the post.

quotemstr 7y ago
In particular, > the real number is not given by an infinite sequence that is actually written down anywhere, but rather as an algorithm, or a black box, which accepts a number n and outputs the n-th digit. At no point do I manipulate an infinite amount of information, yet I can look at any digit I want. Of course, I cannot look at all digits in a finite time, which is sort of the point of the post.

edflsafoiewq 7y ago

A related fact: all functions are defined on closed sets. You cannot "tell" whether a number is in a set or is a limit point of a set. Since all functions are continuous, they work at limit points too. As a "practical" consequence: the common design of a random() function returning values in [0, 1) is wrong. Any function you write cannot "tell" whether it got a 1 or not. These are still very good guidelines even for floating-point code, as long as you, like most everyone else, treat floats as a blackbox abstraction for "real" real numbers.

poizan42 7y ago
Well, random() functions that are normally used are defined on the [0, 1) interval of 32-bit or 64-bit IEEE 754 floating point numbers, for which it is very much computable to determine whether they are exactly 1 (there's nothing "real number" about them though, they all belong to a small finite subset of the rations). Of course that isn't really an open interval in the topological sense either.
- edflsafoiewq 7y ago
  But that's why it's often a bad idea to test exact equality of floats: the equality test isn't continuous. In fact, for float computations it's usually even more important to use continuous (ie. error tolerant) functions, since floating-point operations can introduce errors.
  - saagarjha 7y ago
    Comparing IEEE 754 floating point number is well defined and computable because the domain is discontinuous. It’d be stupid to use anything else…
    - deleted 7y ago
      [deleted]

tel 7y ago

The punchline at the end is worth calling out: Turing Equivalence applies at first-order computations like `Nat -> Nat`, but fails at higher-order computation like `(Nat -> Nat) -> {0, 1}`.

alain94040 7y ago

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?

svat 7y ago

More precisely, all well-defined computable functions are continuous. For another exposition of the same (or similar) results, see also Dan Piponi's post from 2008 "What does topology have to do with computability?" at http://blog.sigfpe.com/2008/01/what-does-topology-have-to-do-with.html http://blog.sigfpe.com/2008/01/what-does-topology-have-to-do... Also, as a follow-up, you may be interested in Martin Escardo's 2007 post on the same blog: http://math.andrej.com/2007/09/28/seemingly-impossible-functional-programs/ http://math.andrej.com/2007/09/28/seemingly-impossible-funct...

carapace 7y ago

Greg Buchholz in the site's comments linked to Gregory Chaitin's "How real are real numbers?"[1] and asks, > Isn't it a little bit crazy to talk about computations on real numbers, when most of them are uncomputable/unnameable? [1] https://arxiv.org/pdf/math/0411418.pdf https://arxiv.org/pdf/math/0411418.pdf > Experimental physicists know how difficult accurate measurements are. No physical quantity has ever been measured with more than 15 or so digits of accuracy. Mathematicians, however, freely fantasize with infinite-precision real numbers. Nevertheless within pure math the notion of a real number is extremely problematic. We’ll compare and contrast two parallel historical episodes: > 1. the diagonal and probabilistic proofs that reals are uncountable, and > 2. the diagonal and probabilistic proofs that there are uncomputable reals. > Both case histories open chasms beneath the feet of mathematicians.

skybrian 7y ago

I'm not a mathematician, but it sounds like what this is saying is that as soon as you allow a number to contain an infinite number of digits, you can get an infinite loop when you try to do a simple comparison. (For example, try to compare pi to an number that's not-quite pi. It might be a little more or a little less, but you can't know this without looking at all the digits, which is impossible.) As a consequence, there are only two boolean-valued total functions: always return true, or always return false. I guess that's why we don't use infinite streams of numbers for computation.

lonelappde 7y ago
You don't need to look at all the digits, but there is no finite stopping point you can choose in advance. It's similar to the problem of comparing two natural numbers given in least significant bit order.
- skybrian 7y ago
  Given a comparison function, an adversary can construct streams of digits that will make it run forever. This would be true either way. The problem seems to be with allowing algorithmically generated streams as input? Maybe our domain should be limited to numbers generated by algorithms that are known to terminate? But despite eliminating irrational numbers, this guarantee doesn't seem like enough for practical computing. Even arbitrary precision algorithms require their inputs not only to be computable, but actually computed in advance, showing at least that they fit in memory.

Nevermark 7y ago

I don't understand the point of arguments about constructible functions on unconstructable reals. I.e. reals with infinite digits and no finite symbolic representation. For anything actually computable (in finite time), on computable (in finite time) values, you will always get discrete (not continuous) functions on discrete (not continuous) values.

vilhelm_s 7y ago
The idea of computable reals go back to at least Turing. The idea is that a real number (or an operation on real numbers) is computable if we can compute the decimal digits, one by one. This way, if the user wants to know it to any desired precision, they just have to wait until the computer has printed that many decimals. You can equivalently treat them as terminating computable functions of type (nat -> bool), which computes the n:th binary decimal. This is actually a quite constructive notion! At least, it works well with intuinistic mathematics, which is why Andrej Bauer is writing about it.
- Nevermark 7y ago
  Ok, that makes sense. Even when restricting numbers to reals with finite symbolic/program definition, comparing two such reals requires an unknown and unbounded number of their digits to be computed. If two symbolic representations define the same number, but it isn't obvious, a complete digit comparison will never end. Got it. Thank you!

mianos 7y ago

This reminds me of the coastline paradox: https://en.wikipedia.org/wiki/Coastline_paradox https://en.wikipedia.org/wiki/Coastline_paradox Specifically, due to the fractal nature of a coastline the length diverges to infinity. The theoretical length at the infinite scale is infinity.

improv32 7y ago

For a very nice into to constructive math, see this[0] link as well as some good HN discussion here[1]. [0]: https://home.sandiego.edu/~shulman/papers/rabbithole.pdf https://home.sandiego.edu/~shulman/papers/rabbithole.pdf [1]: https://news.ycombinator.com/item?id=18411935 https://news.ycombinator.com/item?id=18411935

Gehinnn 7y ago

How do you implement algorithms for real numbers if there uncountable many of them? There is always a real number your algorithm cannot read/process.

lonelappde 7y ago
Algorithms work fine on countable subsets of real numbers, as long as the set you use is discrete at some finite resolution. You only run into trouble if you have no lower bound for separation. It's the same problem even if you have only a countable number of numbers, but you have no lower bound for the smallest positive number or upper bound for the largest number. Even integers are non computable in finite time, one one of them might be arbitrarily large.

loicd 7y ago

The result presented in TFA is that all computable functions over the real numbers are continuous. To generalize that to 'all functions are continuous', you not only need to believe that all functions should be computable, which sounds reasonable for a constructivist, but also that all numbers should be real, which is not. Back when I was in academia, I remember a talk by a mathematician who thought that we should all be doing analysis with rational numbers rather than real numbers. With such a perspective, the sign function defined over rational numbers (e.g. presented as a pair numerator, denominator) is both discontinuous at 0 and computable.