Live data from Hacker News

Turing's topological proof that every written alphabet is finite (2010)

divisbyzero.com

101–110 of 120 posts

Re: Turing's topological proof that every written alphabet is finite (2010)

#101
post #53

I don't agree. What if the next symbol's meaning conditionally depends on the previous ones? For example, in 1937 the third glyph is number three, but in ВАЗ, the third glyph is Cyrillic letter Z. They're not different in writing. It would not be hard to devise a symbolic system where new symbols are context dependent, and there are infinitely many of these depending on the context. The context will be governed by a…

The alphabet itself would still be finite, like our vocabulary.

Our vocabulary is only statistically finite. Number of words in a dictionary is finite. Number of words used to all speakers is not.

Re: Turing's topological proof that every written alphabet is finite (2010)

#102

"I am assuming that the reader is familiar with the terms metric, metric space, topological space, and compact set." On behalf of the math-declined folks, I wish math articles had subtitles, references, and definitions built-in. I wonder if a browser extension for Greek letter definitions would be possible?

The problem is that the definitions of in such footnotes would be full of terms that one also needs defined. For example here's the first few sentences from the Wikipedia page on Compact Sets: In mathematics, specifically general topology, compactness is a property that seeks to generalize the notion of a closed and bounded subset of Euclidean space.[1] The idea is that a compact space has no "punctures" or "missing…

I'd like to see a series of sites or interactive ebooks that work as described below, which would address that problem. I can't actually build such a site or ebook because (1) I'm not sufficiently mathematically sophisticated and (2) my front end skills aren't up to it.

Each one would be devoted to one interesting major mathematical theorem, such as the prime number theorem. The initial view would be a presentation of the theorem as it would be presented if it were a new discover being published in an appropriate journal for the relevant field.

At any point in that view you can pick a term or a step in the proof and ask for it to be expanded. There are two expansion options.

1. More detail. You use this when you understand what is being said but just don't see how they got from A to B. It adds in the missing details.

2. Background. You use a background expansion when you need to know more about some term or theorem that is being used.

I'll give an example of how these might work later.

The details or background you get from either of those expansions can themselves be expanded. Background expansion should work all the way down to pre-college mathematics.

Ideally if you started at the initial view of the prime number theorem site without having had any college mathematics and did background expansions all the way down you would end up learning the necessary calculus and complex analysis and number theory to understand the initial journal-level proof.

You would not learn all of the calculus or complex analysis or number theory one would normally learn in those courses. You would just learn the parts necessary for the top level proof.

I think it would be possible to choose a selection of interesting major theorems to do these sites for such that their combined background expansions would include everything that you'd get in a normal college mathematics degree program.

I think many people would find that a more interesting way to learn the material from a college mathematics degree program than the normal series of courses that each covers one subject. By getting it via background expansions everything you are learning you are learning for a specific application which can be more motivating.

Here's an example of what expansions might do.

There's a theorem from Liouville that says that if a is a real root of an irreducible polynomial with integer coefficiants of degree v >= 2, and p and q are any integers (q != 0) then there is a constant C > 0 which does not depend on p and q such that

  |a-p/q| > C/q^v
In Gelfond's book "Transcendental and Algebraic Numbers" he says (I'm changing the names of some of his variables because I don't want to deal with typing greek letters and some of his terminology for clarity):

> The proof of this is quite straightforward. Suppose a is a real root of an irreducible equation

  f(x) = a0 x^v + ... + av = 0,
> where all of the ai (i = 0, 1, ..., v) are integers. Then, using the mean value theorem, we get

  |f(p/q)| = |a-p/q| |f'(z)| >= 1/q^v; z = a + t(p/q-a),
  |t| 
> from which the Liouville theorem follows directly.

Directly for Gelfond maybe. It certainly does not follow directly for me! I understand everything he's saying, but the steps between some of the things is a little too big for me. I'd need to use a details expansion (maybe more than once). What that should give is something along the lines of how Wikipedia proves that theorem, which is the first lemma in the "Liouville numbers and transcendence" section of their article on Liouville numbers [1].

If I didn't know what the mean value theorem is (or the extreme value theorem, which shows up after expansion to a Wikipedia level of detail) that would be time for a background expansion.

[1] https://en.wikipedia.org/wiki/Liouville_number#Liouville_num...

Re: Turing's topological proof that every written alphabet is finite (2010)

#103

It is even easier to just say, given a fixed area of paper, and a finite printing resolution, there is a finite number of symbols possible? Say you have a 1 in by 1 in area of paper and a printing resolution of 300 DPI then there are 300*300 total dots. If the printer is monochrome and each dot is either black or white then there are 2^(300^2) possible symbols.

I’ve thought about melodies in music too. Obviously, the number of melodies possible is extremely vast. But in 4:4 timing, there must be a limit?

Not only is there a limit, they have been enumerated. And since this is the music industry, copywrited.

https://www.hypebot.com/hypebot/2020/02/every-possible-melod...

Re: Turing's topological proof that every written alphabet is finite (2010)

#104
post #7

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?

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.

Re: Turing's topological proof that every written alphabet is finite (2010)

#105

It is even easier to just say, given a fixed area of paper, and a finite printing resolution, there is a finite number of symbols possible? Say you have a 1 in by 1 in area of paper and a printing resolution of 300 DPI then there are 300*300 total dots. If the printer is monochrome and each dot is either black or white then there are 2^(300^2) possible symbols.

I’ve thought about melodies in music too. Obviously, the number of melodies possible is extremely vast. But in 4:4 timing, there must be a limit?

The number of notes per bar is not really finite given you can make any a:b polyrhythm and you can make any subdivision you like. For example, see the famous falling coin rhythm based on the Fibonacci series in Bartok's "Music for Strings, Percussion and Celeste"[1]

[1] If you want a look at what "Pyramids on Mars"-style musical analysis is like, Erno Lendvai's book about Bartok is pretty awesome. Since Bartok never really wrote or said anything about his compositional methods it's very hard to prove anything conclusively.

Re: Turing's topological proof that every written alphabet is finite (2010)

#106
post #14

Earlier quoted context omitted.

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.

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.

> 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.)

Re: Turing's topological proof that every written alphabet is finite (2010)

#107
post #54

Earlier quoted context omitted.

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.

Re: Turing's topological proof that every written alphabet is finite (2010)

#108
post #14

Earlier quoted context omitted.

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.

> 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 (delightfu…

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.

Re: Turing's topological proof that every written alphabet is finite (2010)

#109

Earlier quoted context omitted.

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 =)

Re: Turing's topological proof that every written alphabet is finite (2010)

#110

> The human eye cannot tell two symbols apart when they are too similar. That leads to a simple information-theory based argument. There is a limited spatial resolution and noise floor, and so the amount of information that can be coded is finite.

I feel like this fact from information theory also requires its own proof, and one strategy for that is likely to be similar to Turing's!
Post reply on HN