4 ms·

> A much more interesting question is whether the space of binary streams is compact, but that is another story. I don't know very much about topology, so I'm

> A much more interesting question is whether the space of binary streams is compact, but that is another story. I don't know very much about topology, so I'm having some trouble understanding what his means. How are open sets defined in the space of binary streams? What would be the implications of this space being compact?

eigenket 5y ago
Yeah I have no idea what the author is getting at there. One obvious way to put a topology on the space of binary streams is to think of them as binary expansions of real numbers in the interval [0, 1] (the notation is supposed to indicate that we include 0 and 1) and inherit the topology from the normal topology on the reals in which case the answer is yes [0,1] is compact. In this representation 0 is included as the binary stream consisting of all zeros and 1 is included as the binary stream consisting of all 1s. This isn't entirely clean as a bunch of (rational) real numbers in [0,1] have multiple different binary expansions, for example 1/2 can be written .10000... (the zeros go on forever) or .01111... (the ones go on forever)
- chas 5y ago
  This is likely what he is referring to: http://math.andrej.com/2007/09/28/seemingly-impossible-functional-programs/ http://math.andrej.com/2007/09/28/seemingly-impossible-funct... In particular, you can search compact infinite spaces by only considering a finite number of steps: "What is going on here is that computable functionals are continuous, which amounts to saying that finite amounts of the output depend only on finite amounts of the input. But the Cantor space is compact, and in analysis and topology there is a theorem that says that continuous functions defined on a compact space are uniformly continuous. In this context, this amounts to the existence of a single `n` such that for all inputs it is enough to look at depth `n` to get the answer (which in this case is always finite, because it is an integer). I’ll explain all this in another post. Here I will illustrate this by running the program in some examples." This is the follow-up post mentioned in the quote: http://math.andrej.com/2008/11/21/a-haskell-monad-for-infinite-search-in-finite-time/ http://math.andrej.com/2008/11/21/a-haskell-monad-for-infini...
- anderskaseorg 5y ago
  You can avoid the problem of multiple expansions by using base 3 numbers that don't contain the digit 2. The resulting space is equivalent to the Cantor space mentioned in other comments.
creata 5y ago
I think the relevant topology on the space of binary streams is the Cantor space.[0] It's compact, and can be seen as a subspace of the real line.[1] The fact that it's compact is equivalent to a principle called the fan theorem, which is simply true in classical mathematics, but which different schools of constructive mathematics don't agree on.[2] [0]: https://ncatlab.org/nlab/show/Cantor+space https://ncatlab.org/nlab/show/Cantor+space [1]: https://en.wikipedia.org/wiki/Cantor_set https://en.wikipedia.org/wiki/Cantor_set [2]: https://ncatlab.org/nlab/show/fan+theorem https://ncatlab.org/nlab/show/fan+theorem
obastani 5y ago
I'm not sure what the author has in mind, but a standard way to put a topology on this space would be to use the discrete topology [1] on {0, 1}, and then use the product topology [2] to obtain a topology over the space of binary streams. This space is homeomorphic to the Cantor set (see "Examples" section in [2]), so you can think of it as being the same topology as the Cantor set. [1] https://en.wikipedia.org/wiki/Discrete_space https://en.wikipedia.org/wiki/Discrete_space [2] https://en.wikipedia.org/wiki/Product_topology https://en.wikipedia.org/wiki/Product_topology
kmill 5y ago
There's an interesting branch of math called "synthetic topology" where you study computational questions topologically. https://ncatlab.org/nlab/show/synthetic+topology https://ncatlab.org/nlab/show/synthetic+topology Given a set X of things that can be encoded for a Turing machine, consider the semidecidable subsets (those subsets of things for which a there's a Turing machine that will halt if and only if it's given one of them). This forms a basis for a topology; it has finite intersections because you can run two Turing machines in parallel. So, a subset S of X is considered to be open if every element p in S has a Turing machine that halts for p, and whenever it halts for any other element, that element is in S. Given this topology, what does it mean to be compact? It means whenever you have a collection of Turing machines (possibly infinite!) such that for every element of X there's a Turing machine that halts for it, then there's some finite sub-collection of Turing machines with the same property. The space of binary streams can be encoded as plain old Turing machine tapes (maybe give it to the Turing machine as a second tape for convenience). If a Turing machine halts given a tape, then it only looked at some prefix of the stream to make the decision, so it will also halt if you change anything outside that prefix. This corresponds to the usual product topology, with the basic Turing machines being "check that the stream has this fixed prefix." The space is a product of finite sets, so by the Tychonoff theorem it's compact. An application of this is the following. Suppose you have a computable function f : binary streams -> bool. That is, you have a Turing machine that halts for every binary stream, resulting in either True or False. You can think of this as being two Turing machines, one that recognizes when f returns True (otherwise it artificially goes into an infinite loop), and similarly another that recognizes when f returns False (otherwise loops). Both of these Turing machines define open subsets of the space of binary streams, the union of which is the whole space of binary streams. Since they are open, they are all unions of all the basis sets of the product topology (recall: sets of all binary sequences with a common prefix). Since the space is compact, you only need finitely many of these basis sets -- let n be the longest prefix. Hence, there is a Turing machine for f that makes its decision by looking at only a prefix of a fixed length n of the binary stream!
- thomasahle 5y ago
  I'm trying to follow you last example. It seems you are proving that for any computable function `f`, there is a number `n` such that f can be computed by never looking at more than the first `n` bits of the input? I thought that would fail for a simple function like "Does the stream include a 1", which takes finite time for any stream that includes a "1", but doesn't use a bounded prefix. I guess restricting the input this way somehow makes the set not open?

eigenket 5y ago

Yeah I have no idea what the author is getting at there. One obvious way to put a topology on the space of binary streams is to think of them as binary expansions of real numbers in the interval [0, 1] (the notation is supposed to indicate that we include 0 and 1) and inherit the topology from the normal topology on the reals in which case the answer is yes [0,1] is compact. In this representation 0 is included as the binary stream consisting of all zeros and 1 is included as the binary stream consisting of all 1s. This isn't entirely clean as a bunch of (rational) real numbers in [0,1] have multiple different binary expansions, for example 1/2 can be written .10000... (the zeros go on forever) or .01111... (the ones go on forever)

chas 5y ago
This is likely what he is referring to: http://math.andrej.com/2007/09/28/seemingly-impossible-functional-programs/ http://math.andrej.com/2007/09/28/seemingly-impossible-funct... In particular, you can search compact infinite spaces by only considering a finite number of steps: "What is going on here is that computable functionals are continuous, which amounts to saying that finite amounts of the output depend only on finite amounts of the input. But the Cantor space is compact, and in analysis and topology there is a theorem that says that continuous functions defined on a compact space are uniformly continuous. In this context, this amounts to the existence of a single `n` such that for all inputs it is enough to look at depth `n` to get the answer (which in this case is always finite, because it is an integer). I’ll explain all this in another post. Here I will illustrate this by running the program in some examples." This is the follow-up post mentioned in the quote: http://math.andrej.com/2008/11/21/a-haskell-monad-for-infinite-search-in-finite-time/ http://math.andrej.com/2008/11/21/a-haskell-monad-for-infini...
anderskaseorg 5y ago
You can avoid the problem of multiple expansions by using base 3 numbers that don't contain the digit 2. The resulting space is equivalent to the Cantor space mentioned in other comments.

creata 5y ago

I think the relevant topology on the space of binary streams is the Cantor space.[0] It's compact, and can be seen as a subspace of the real line.[1] The fact that it's compact is equivalent to a principle called the fan theorem, which is simply true in classical mathematics, but which different schools of constructive mathematics don't agree on.[2] [0]: https://ncatlab.org/nlab/show/Cantor+space https://ncatlab.org/nlab/show/Cantor+space [1]: https://en.wikipedia.org/wiki/Cantor_set https://en.wikipedia.org/wiki/Cantor_set [2]: https://ncatlab.org/nlab/show/fan+theorem https://ncatlab.org/nlab/show/fan+theorem

obastani 5y ago

I'm not sure what the author has in mind, but a standard way to put a topology on this space would be to use the discrete topology [1] on {0, 1}, and then use the product topology [2] to obtain a topology over the space of binary streams. This space is homeomorphic to the Cantor set (see "Examples" section in [2]), so you can think of it as being the same topology as the Cantor set. [1] https://en.wikipedia.org/wiki/Discrete_space https://en.wikipedia.org/wiki/Discrete_space [2] https://en.wikipedia.org/wiki/Product_topology https://en.wikipedia.org/wiki/Product_topology

kmill 5y ago

There's an interesting branch of math called "synthetic topology" where you study computational questions topologically. https://ncatlab.org/nlab/show/synthetic+topology https://ncatlab.org/nlab/show/synthetic+topology Given a set X of things that can be encoded for a Turing machine, consider the semidecidable subsets (those subsets of things for which a there's a Turing machine that will halt if and only if it's given one of them). This forms a basis for a topology; it has finite intersections because you can run two Turing machines in parallel. So, a subset S of X is considered to be open if every element p in S has a Turing machine that halts for p, and whenever it halts for any other element, that element is in S. Given this topology, what does it mean to be compact? It means whenever you have a collection of Turing machines (possibly infinite!) such that for every element of X there's a Turing machine that halts for it, then there's some finite sub-collection of Turing machines with the same property. The space of binary streams can be encoded as plain old Turing machine tapes (maybe give it to the Turing machine as a second tape for convenience). If a Turing machine halts given a tape, then it only looked at some prefix of the stream to make the decision, so it will also halt if you change anything outside that prefix. This corresponds to the usual product topology, with the basic Turing machines being "check that the stream has this fixed prefix." The space is a product of finite sets, so by the Tychonoff theorem it's compact. An application of this is the following. Suppose you have a computable function f : binary streams -> bool. That is, you have a Turing machine that halts for every binary stream, resulting in either True or False. You can think of this as being two Turing machines, one that recognizes when f returns True (otherwise it artificially goes into an infinite loop), and similarly another that recognizes when f returns False (otherwise loops). Both of these Turing machines define open subsets of the space of binary streams, the union of which is the whole space of binary streams. Since they are open, they are all unions of all the basis sets of the product topology (recall: sets of all binary sequences with a common prefix). Since the space is compact, you only need finitely many of these basis sets -- let n be the longest prefix. Hence, there is a Turing machine for f that makes its decision by looking at only a prefix of a fixed length n of the binary stream!

thomasahle 5y ago
I'm trying to follow you last example. It seems you are proving that for any computable function `f`, there is a number `n` such that f can be computed by never looking at more than the first `n` bits of the input? I thought that would fail for a simple function like "Does the stream include a 1", which takes finite time for any stream that includes a "1", but doesn't use a bounded prefix. I guess restricting the input this way somehow makes the set not open?