How does topology show up in computation? An introduction from first principles.
Topology is the branch of mathematics that studies the notion of continuous function, and then everything that follows from that, and, more importantly, that, in the first place, sets the scene to be able to define the notion of continuity in full generality.
Originally, the notion of continuity was used (without a definition!) for functions ℝ → ℝ. At some point in the 19th century we had a definition.
And then people considered continuity of more general functions, e.g. ℝⁿ → ℝ, or C(ℝ) → ℝ where C(ℝ) is the set of all continuous functions ℝ → ℝ, and much more.
One interesting example, for computation, is the Cantor set (or Cantor space).
One way to describe it is as a subset of ℝ (https://en.wikipedia.org/wiki/Cantor_set), which you probably have seen as Cantor's third-middle set.
An isomorphic copy (or homeomorphic copy, as topologists would say) that often occurs in computation is as infinite binary sequences.
Technically, this is "the topological product of countably many copies of the discrete space {0,1}". One aim of this discussion is to make this technical definition more understandable if you don't have a background in Topology.
Consider a computer that keeps reading 0's and 1's and outputting 0's and 1's forever. For example, the program can be
while (true) {
b := read a binary digit;
print (1-b);
}
This program is an example of a continuous function from the Cantor space to the Cantor space.
1/
A more sophisticated example of such a program would be one that keeps reading, bit by bit, the binary expansion of a real number x in the interval [0,1] (imagine the input sequence dₙ as standing for the number 0.d₀d₁d₂ ⋯ dₙ ⋯ in binary notation) and prints, bit by bit, the binary representation of 3x/4 (we divide by 4 so that the output remains in the same interval and hence we can use the same notation, for simplicity).
Theorem (of computability theory). No such program exists.
However, the function 1-x from [0,1] to [0,1] is computable, by the above program. What is going on? What's the problem? And is there a way to fix it? Or not?
Theorem (of computability theory). Any program that inputs infinite binary sequences and outputs infinite binary sequences, digit by digit, defines a *continuous* function from the Cantor space to itself.
Theorem (of topology). A function from the Cantor space to itself is continuous if and only if it is of "finite character" in the following sense: In order to know a finite amount of the output of the function, it is enough to know a finite amount of the input of the function.
So here is a simple counter example to continuity: consider the function whose first digit of output is 0 (followed by something else we don't care) if the input sequence is all 0's, and whose first digit of output is 1 (again followed by something else we don't care) otherwise. To compute such a function, you would need a crystal ball.
2/
It turns out that to compute 3x/4, in binary, you also would need a crystal ball. This was discovered by Brouwer in his paper
"L.E.J. Brouwer. Besitzt jede reelle Zahl eine Dezimalbruchentwicklung? Math Ann, 83:201–210, 1920.",
which asks whether every real number has a decimal expansion.
So let's look at the 3x/4 problem in decimal, only because we are more used to this notation, and the variation 3x/10 of the function (which is what Brouwer did).
We want to compute 3x, in decimal, by a program that keeps reading decimal digits, one by one, and keeps outputting decimals digits, one by one.
Now suppose you have read 0.3333 from the input so far.
What should the first digit of output be? We don't know. If the next digit is 2, then our output should start as "0.9". But if the next digit is 4, then our output should start as "1.". And if the next digit is "3", we don't know. And if all following digits happen to be 3, then, without a crystal ball, we won't be able to produce any single digit of output.
But Brouwer didn't stop there. He also showed how to solve the problem. I am not going to discuss his solution.
But it is worth mentioning that Cauchy had solved the problem himself before, without trying to solve this particular problem. He observed that if we allow negative decimal digits, then computations by hand are simplified.
A. Cauchy. Sur les moyens d’ ́eviter les erreurs dans les calculs num ́eriques. Comptes Rendus 11, pages 789–798, Paris 1840. Republished in: Augustin Cauchy, Œvres compl`etes, 1 ́ere s ́erie, Tome V, pp 431–442.
3/
There is a lot more to say. But the main message is that "finite amounts of output depend only on finite amounts of input" amounts to continuity in the topological sense.
This allows one to apply topology to discover new things about computation, and much of my work is based on this.
For example, what does the notion of compactness mean in computation, and how can we use theorems in topology that mention compactness in topology to learn something new about computation. And more.
4/
In order to show the impact of topology in computation, here I give an incomplete list of things I wrote about this, where you can find references to the work of many other people.
(1) A Haskell program (from long ago) that prints π for every (in decimal, in signed binary and more), that integrates functions "exactly" by computing correct digits for ever, and more: https://www.cs.bham.ac.uk/~mhe/papers/fun2011.lhs
(2) An old blog post from 2007 called "Seemingly impossible functional programs" that exploits continuity and compactness: https://math.andrej.com/2007/09/28/seemingly-impossible-functional-programs/
(3) A long paper from 2004 called "synthetic topology of data types and classical spaces": https://www.sciencedirect.com/science/article/pii/S1571066104051357
(4) A paper "Infinite sets that admit fast exhaustive search": https://www.cs.bham.ac.uk/~mhe/papers/exhaustive.pdf
(5) A paper "Exhaustible sets in higher-type computation" which proves all of the above , and more, in a rigorous, Bourbakian way, using domain theory in addition to topology: https://lmcs.episciences.org/693
Among others I've written over the year.
/5
I don't have time right now, but I will write a follow-up thread discussing what topology has to say regarding (exact) real-number computation.
Representations of real numbers suitable for (exact) computation have topological characterizations as "admissible" (topological) quotient representations.
6/6
@MartinEscardo You skipped the word "impossible" in "seemingly functional programs".
@oantolin Thanks! Fixed.
@MartinEscardo due to my limited background in computation it took me a bit longer than usual to understand this thread! Thanks! Maybe my knowledge of topology can continue to serve as an entry point.
@MartinEscardo We could print 0,999... and if all the input turns out to be 3s, then all the output turns out to be 9s, which is a valid representation of 1. Or do we outlaw that expansion here?
@bioinfochat It's not outlawed, but this still doesn't work: if you eventually see a digit 4 or bigger you will be in trouble.
@MartinEscardo ah, I see now. So where does this leave us? Is multiplication of real numbers not computable?
@bioinfochat It is computable, but you need to use a different representation, such as decimal with negative digits, as proposed by Cauchy. (But there are other representations that work equally well.)
@MartinEscardo in the first paragraph are you saying it prints out 3x/4 where x is the current bit of input? Also what do you mean we divide by 4 so the output stays in the same interval? Sorry for the naive question
Here x = 0.d₀d₁d₂ ⋯ dₙ ⋯ is the binary expansion of a real number x in [0,1].
Then you can ask about the function sending x to 3x, but this sends the interval [0,1] to the interval [0,3]. This is an issue since we want to keep the same encoding of binary strings as reals in [0,1] for the whole problem. We can sidestep this by dividing by 4 to make sure our output lands in [0,1].
So altogether we're considering the function [0,1] to itself sending x to 3x/4. And we're encoding these reals by infinite bitstrings.
As one other observation, whatever goes wrong here really has something to do with the multiplication by 3, not the division by 4. After all, x/4 is continuous, and is implemented as a bit shift!
(Also, later in the thread, we switch to working with base 10 expansions instead of base 2 expansions. This is slightly easier for us to think intuitively about, and doesn't really change the math)
@hallasurvivor @MartinEscardo oh duh. Lol. Thank you!
@MartinEscardo Woooow, great thread. Can keep one busy for anything between 2 minutes to 2+ decades! Thanks for sharing