Representations of Uncomputable and Uncountable Sets (2008) | Hacker News Reader

Representations of Uncomputable and Uncountable Sets (2008)

math.andrej.com

45 pointscreata9 comments

> 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?

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)

.01111... (the ones go on forever)

This is likely what he is referring to: 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-infini...

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.

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

[1]: https://en.wikipedia.org/wiki/Cantor_set

[2]: https://ncatlab.org/nlab/show/fan+theorem

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

[2] https://en.wikipedia.org/wiki/Product_topology

There's an interesting branch of math called "synthetic topology" where you study computational questions topologically. 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!

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?

Indeed, computable functions on binary streams have a uniform bound on how much of a stream they'll look at!

"Does this stream include a 1" is not computable, since it won't halt on 00000.... The subset of streams that include a 1 is open, though.

If you restrict to the subset of streams that include a 1, then computable functions might look at some unbounded amount of the input (example: is the value after the first 1 a zero? this is computable but takes unbounded time). This doesn't contradict anything because this subset is not compact.

Here's another interesting application (not fully fleshed out here). An arbiter is a computable function that watches a stream of messages produced by a distributed system and decides whether the consensus reached is A or B. Suppose each process only sends messages from a finite set (they're TCP packets or something). The space of message streams is compact, so by the same argument the arbiter makes its decision within a fixed amount of time, independent of the message stream. If messages can be delayed or lost and there are at least two processes, then the arbiter has to always answer only A or B, since otherwise it would be possible to construct two message streams that have the same prefix, but impossibly the arbiter answers A for one and B for the other.

Reply on news.ycombinator.com