2 ms·
I have to make a correction in my earlier comment (can't edit any more). I previously stated that this has nothing to do with topology or continuous functions o
by kccqzy 8y ago
I have to make a correction in my earlier comment (can't edit any more). I previously stated that this has nothing to do with topology or continuous functions or compactness but in fact it does. It's actually a kind of Baire space. I'll try to more precisely explain this part that's only vaguely told as a story in the original article.
So topologically a continuous function (from a topological space to another) is defined as one where the preimage of every open set is open. (This definition for real numbers is equivalent to the traditional epsilon-delta definition.)
Now for bit sequences we can define a topology via neighborhoods: a neighborhood of a bit sequence is simply those that share a finite prefix. Then an open set means that for every point (bit sequence) in it, there's a finite prefix such that all sequences with this finite prefix are in the open set. Compare this with the traditional open set definition for real numbers: a set is open if for every real number in it, there's an epsilon-neighborhood such that all real numbers within this neighborhood are in the open set. In fact it's the same definition once we choose a definition for neighborhoods.
Then for booleans we just use the discrete topology so any subset is open.
So what I was saying in the parent comment (function only examining a finite prefix to produce a boolean) basically implies that it's continuous: for every possible output boolean, the preimage must consist of a union of neighborhoods with finite prefixes. So if a function only examines a finite prefix of a bit sequence, its preimage cannot be more than a union of neighborhoods.
(On the other hand, it is possible that a function chooses to examine more than just a finite prefix and still be continuous. In this case we don't know that the function will throw away information gleaned from examining the infinite sequence. It just won't terminate.)