[HN Gopher] Representations of Uncomputable and Uncountable Sets...
___________________________________________________________________
Representations of Uncomputable and Uncountable Sets (2008)
Author : creata
Score : 43 points
Date : 2021-07-30 13:52 UTC (9 hours ago)
(HTM) web link (math.andrej.com)
(TXT) w3m dump (math.andrej.com)
| bkallus wrote:
| > 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?
| obastani wrote:
| 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
| eigenket wrote:
| 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 wrote:
| 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...
| anderskaseorg wrote:
| 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 wrote:
| 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
| kmill wrote:
| 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!
| thomasahle wrote:
| 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?
| kmill wrote:
| 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.
___________________________________________________________________
(page generated 2021-07-30 23:01 UTC)