Hacker News Reader

Comment by Smaug123 | Hacker News Reader

That works if you're fixed to a grid, but the argument is much more general: it allows symbols to be of arbitrary size (as long as they're still within the unit square), in any orientation, formed by continuous or (not-too-pathological) discontinuous penstrokes, etc.

View on HN

It doesn't, however, allow for non-closed symbols. I can imagine a spiralling brushstroke that gets fainter as it approaches the centre. Maybe the proof can be strengthened, and it certainly won't pass the distinguishability criterion, but we must be rigorous, here if anywhere.

Why should it not allow for your spiralling brushstroke? You can divide the spiral into the strokes corresponding to each turn around the center. We can assume that each of these strokes is measurable (otherwise we would not need the construction of the spiral). Then the entire spiral is just a countable union of those measurable strokes, thus it is measurable itself.

For the proof given in TFA they use the assumption that the symbol is compact and hence closed. I argue that the symbol needn't be closed, it may still be measurable.

> here if anywhere

:-D

We can play a lot of games with "what is a symbol", but compactness pervades many of the models that we use to describe reality. The crux of the argument is not necessarily that the symbols themselves are compact as sets, but that the *space of possible descriptions* is compact. In the article, the space of descriptions is (compact) subsets of a (compact) two-dimensional space, which (delightfully) is compact in the appropriate topology.

In your example, the symbols themselves could instead be modeled as a function f:[0,1]^2 -> [0,1] which are "upper semicontinuous", which when appropriately topologized is seen to be compact; in particular, every infinite sequence must have a subsequence that converges to another upper semicontinuous function.

Much of the fun here comes from the Tychonoff theorem, which says that arbitrary products of compact spaces is compact. Since the *measurement space* is compact, the topology of the domain is not as important, as long as the product topology on the function space is the appropriate one. (Mystically, it almost always is.)

The proof defines F(X) as the set of compact subsets of X (here the unit square). The compactness of F(X) follows from (necessary?) the compactness of its elements, so we need to find a topology where all our allowable symbols are compact, and this is not the standard topology if you allow the spiral. If you take another topology (equivalently space of symbol descriptions) then you again must show that this compactness still corresponds to the desired notion of "distinguishability".

My topology is rusty and I don't genuinely doubt the validity of the argument, but I'm having fun trying to poke holes.

Your example centered on a symbol which, if viewed as a subset of the plane, is not compact. I tried to argue that the set of symbols that you describe (ink of varying levels of intensity in the unit square) still is a compact set, even though the symbols themselves are no longer represented by compact sets.

The proof doesn't assume that they are formed by not-too-pathological penstrokes.

<wrong>The idea is that you should measure the amount of black and white ink to change a symbol into another simbol, and if the total amount of ink is less than ε then they indistinguishable. (Where ε is some constant you must choose for the whole system.)</wrong>

I think that every horrible-totally-pathological ink splash has a nice indistinguishable version, but my real analysts is a bit rusty, and there are a few horrible things that I may have forgotten.

Edit: see comment below.

By "not-too-pathological" I intended at least to include the requirement "measurable".

I just notice that I used the wrong metric. The article uses the Hausdorf metric and I used the measure of the symetric difference.

And the article assume that the sets are compact, so they are measurable as you say. Anyway compact sets can be quite pathological (but not as pathological as non measurable sets).

It also suggests the argument generalizes to symbols as non-compact sets.

I made a comment elsewhere on this thread that explains that symbols themselves being compact isn't so important, but that the set of descriptions of the symbols must be compact. For example, if the description of the symbol is not the symbol itself as a set, but a map f:[0,1]^2 -> [0,1] that describes the "intensity" of ink at each point, then the natural conclusion is that the description of a symbol must be upper semicontinuous, which makes the set of descriptions compact.

Reply on news.ycombinator.com