Hacker News Reader

Comment by tempfile | Hacker News Reader

Turing's argument says "conditionally compact" but the article talks only about "compact". They are not the same; "conditionally compact" means every sequence has a Cauchy subsequence, while (sequentially) compact means every sequence has a convergent subsequence. If the metric space Turing mentions is complete, then I guess they're the same. Is that obvious?

View on HN

Convergent sequences are always Cauchy; for metric spaces, compactness and sequential compactness are the same.

I think the question is more like:

> Turing says that a certain space, the space of all compact subsets of [0,1]^2 endowed with the metric "integral of minimal distance required to transform {1 ink at each point of P1} u {infinite amount of ink at (2, 0)} into {1 ink at each point of P2} u {infinite amount of ink at (2,0)}", is conditionally-compact. How is that related to the article's argument?

This is not obvious, I think. The article has moved away from Turing's "integral of the distance we have to transfer ink", instead using "maximum distance we have to transfer any ink", and I don't have a great intuition for whether this is a legit transformation of the argument. (I'm sure both proofs are correct, but it's not obvious to me that they are the same proof.)

Yes and yes, but conditional compactness is different, and Cauchy sequences are not always convergent. That's why I mentioned completeness.

Given any compact metric space $(M, d)$ (which in the article is the closed unit square), the set of non-empty compact subsets of $M$ under the Hausdorff metric $h$ is also a compact metric space.

Are the symbols assumed to be compact? I guess their closures obviously are, and the closure of a symbol should be indistinguishable from the symbol.

Yeah, seems like Turing defines a symbol to be a compact subset of the unit square. Whether that makes sense or not to you is up to interpretation I guess, but like you say the closure should be more or less the same as the symbol for "reasonable" symbols.

You then need to assume that each symbol has some variation in how it's written, I think, which you can think of as an open set in the symbol-space (which is compact under $h$ as per my previous comment). The collection of all these opens forms a cover of the symbol-space, which by compactness must have a finite sub-cover (Turing's "alphabet").

A very elegant bit of philosophy imo =)

Reply on news.ycombinator.com