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

https://divisbyzero.com/2010/05/27/turings-topological-proof-that-every-written-alphabet-is-finite/

by aebtebeten • 2 years ago

138 114 2 years ago

ainoobler8• 2 years ago

Interesting argument. This assumes that cognition must also be happening on a compact manifold which seems like a reasonable assumption but the conclusion is somewhat counterintuitive because it means there are only finitely many personality types and ways of thinking.

Vecr• 2 years ago

That's how the math works out in general unless you think some kind of soul exists.

ainoobler8• 2 years ago

It all follows from compactness so if the cognitive manifold is not compact then the conclusion is not true.

andoando• 2 years ago

At this point I kind of do. The matter that goes into forming your body and brain is somewhat special, having accumulated the properties it has experiencing billions of years of traveling through the universe.

Once you die it decomposes and goes on its way, and forms something new.

Its not a "soul" in the same sense but still pretty trippy

Smaug1239• 2 years ago

Is that counterintuitive? There's a finite number of electrons in a human brain (which fits in a space of size 1m^3), and information takes time to propagate across any distance, and humans die before 150 years; this all gestures at there being not only finitely many personality types and ways of thinking, but finitely many human mind states.

ainoobler8• 2 years ago

I guess that means reincarnation is real.

Y_Y6• 2 years ago

But there may yet be more brain states than number of possible thoughts by the finite humans.

tempfile6• 2 years ago

Who said this had anything to do with cognition at all? I think Turing's argument goes through with humans replaced by automata and eyes by cameras. It's just that perception has finite resolution.

ainoobler8• 2 years ago

I made the obvious connection. It's an original thought from me and no one else.

aiauthoritydev• 2 years ago

Well, this is true only if you think cognition and thought as a pure biological process totally dependent on state of brain.

ainoobler8• 2 years ago

I don't think that. I'm just explaining what follows logically if the cognitive manifold is compact.

nxobject• 2 years ago

Just a reading note to myself: the key assumption is that there is a "resolving limit" \epsilon such that symbols that are "closer and smaller" than \epsilon are indistinguishable. The implicit assumption there is that you can resize symbols while keeping them the same.

andrewflnr2• 2 years ago

I'm not sure that assumption is necessary, at least for finitely sized alphabets. For finitely many sizes of symbol that are meant to be distinguishable, you can define the smaller ones as just taking up smaller portions of the square. If you try to scale down too far, they'll eventually hit the epsilon limit and be indistinguishable again. Maybe you could break the theorem by growing arbitrarily large, but that really stretches the word "alphabet". He was thinking of notebook pages, so encoding things in the size of arbitrarily large symbols wasn't top of mind.

contravariant• 2 years ago

I dunno, somehow the conclusion that an infinite alphabet requires symbols to grow arbitrarily large to allow them to be distinguished from the others doesn't seem quite as interesting as the conclusion that all written alphabets are finite.

I mean clearly you can design an infinite alphabet by just using numbers for all symbols and writing the numbers in whatever system you want. Sure some symbols will require more paper or their details become too small to see, but it is still an infinite written alphabet.

The more obvious argument is that an infinite alphabet is pointless because nobody can remember an infinite list of symbols (hence any practical example of such an alphabet must have some rules to reduce the symbols to a finite set of atoms). There's nothing theoretically impossible about one existing.

montecarl• 2 years ago

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.

grvbck• 2 years ago

Next week on Show HN: I made a fractal font with unlimited scaling

perihelions• 2 years ago

You can take a glyph from that font, cut up and rearrange it, and come out with two copies of the original size. Saves money on printer ink

kazinator3• 2 years ago

The closed-form math formulas giving the glyphs of the font have to be written on a square piece of paper with limited resolution ...

daedalus_j• 2 years ago

The Minds from The Culture scifi series have something like this... The top level glyph is the base meaning and you can encode essentially infinite depth of meaning beyond that... Of course you have to go multidimensional at some point, so you can't really print it out beyond a few layers of resolution...

Smaug1239• 2 years ago

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.

Y_Y6• 2 years ago

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.

gus_massa2• 2 years ago

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.

ertgbnm• 2 years ago

Yes it's easier and not too different from Turing's argument. However, Turing made this proof in 1936, you know, before the concept of pixels exists.

Y_Y6• 2 years ago

Not far off though, "pix" was in use by at least 1932, and "pixel" by 1956[0].

[0] https://en.wikipedia.org/wiki/Pixel

kragen2• 2 years ago

nyquist's sampling theorem is from 01915. western union started offering wirephoto service in 01921, and the associated press started mass distribution of news photos in 01935. these aren't discrete pixels but they did demonstrate that nyquist's sampling theorem applies to images too

tempfile6• 2 years ago

Approximating an arbitrary shape by covering it with tiny squares is not exactly new. The method of exhaustion goes back to 200BC.

throwawayffffas• 2 years ago

The Planck length has been a thing since 1899.

kmoser2• 2 years ago

The article ends by noting that even with colored ink, the number of distinguishable symbols is finite. Indeed, if there is a limit to the number of values held by each of the variables, that would limit what you could write.

If we're looking for theoretical ways around that constraint, you could allow inks that change over time, so you would have to observe each character for a certain amount of time in order to see what it was representing as its ink changed (or didn't).

codeflo• 2 years ago

If the observation time is finite, and the time resolution of the observation is limited, then you'd still only have a finite number of distinguishable symbols, wouldn't you?

passion__desire2• 2 years ago

For some reason, I am thinking about the green-blue and grue-bleen paradox.

https://en.wikipedia.org/wiki/New_riddle_of_induction

The "New Riddle of Induction," proposed by Nelson Goodman in 1955, challenges our understanding of inductive reasoning and the formation of scientific hypotheses. Goodman introduced the concept through his famous "grue" example. Imagine a property "grue," defined as "green up to time t, and blue thereafter." All emeralds examined before time t are both green and grue. The riddle asks: Why is it rational to predict that future emeralds will be green rather than grue? This paradox highlights the problem of choosing between competing hypotheses that equally fit past observations. It questions our basis for preferring "natural" predicates (like green) over "artificial" ones (like grue) in inductive reasoning. Goodman's riddle challenges the idea that induction is based solely on observed regularities. It suggests that our choice of predicates in forming hypotheses is influenced by factors beyond mere observation, such as simplicity, familiarity, or projectibility. The New Riddle of Induction has significant implications for philosophy of science, epistemology, and artificial intelligence. It raises questions about the foundations of scientific prediction, the nature of natural kinds, and the role of language in shaping our understanding of the world.

https://x.com/eshear/status/1812926436623413285

There are crystal structures that simply won't form anymore, even though they did a few decades ago. Real life Ice-9? Could make an incredible sci-fi book.

kazinator3• 2 years ago

You also have to argue for finite color resolution, or else a color noise floor that masks the difference between similar colors.

If we have 300 dpi, we can still code unlimited amounts of information if the color space is continuous, and noise-free.

(The article mentions the human eye limitations, but we could use technological instrumentation to extract info from a print; the human eye doesn't limit what we can code on a BluRay disc, e.g.)

refulgentis• 2 years ago

Print resolution is far higher than 300 DPI, floor for the cheapest is 1000, most will do 4K. (not a correction, I am only sharing this because I think of this often because it seems leverage-able for something unique, and HN is a good place to share that sort of thing, in case someone is inspired)

snthpy3• 2 years ago

I totally agree with your argument. However just to throw out an idea for a possible counterexample (as mathematicians like to do):

What if you used aperiodic Penrose tiles and could detect intensity? Would it be possible to encode anything in that? There would be no repetition but when would you hit limits of discernability with all the overwriting?

snthpy3• 2 years ago

I mean the number of tiles is finite but what if the alphabet was the encoded in the geometrical arrangement of the tiles?

bamboozled• 2 years ago

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?

SideburnsOfDoom• 2 years ago

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

seanhunter• 2 years ago

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.

tempfile6• 2 years ago

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?

dbfclark• 2 years ago

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

Smaug1239• 2 years ago

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

tempfile6• 2 years ago

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

bubblyworld2• 2 years ago

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.

tempfile6• 2 years ago

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.

thriftwy4• 2 years ago

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 finite number of rules. The glyphs will not change meaning in a specific text.

Human language is an example of such system. If you treat words as a whole as symbols, you can have infinitely many different words as they become defined via the specific text, but obviously you can't have infinitely many different words in a single text because they will stop being mutually intelligible at some point.

Smaug1239• 2 years ago

Of course you can have infinitely many different semantics, but this is a question about available syntaxes. (Trivial proof: for each n, take the semantics S_n which assigns to the symbol "X" the meaning "integer n", just as English usually assigns to the symbol "3" the meaning "integer 3".)

thriftwy4• 2 years ago

I'm not sure I follow. Natural languages usually have very simple syntax. The Greeks had great literature while still in "boustrophedon with no whitespace" phase.

The number of possible symbol meanings may be unbound. And there may be symbol definition rules so that any effective symbol set used to write a text is still plausibly an alphabet. Chinese actually does fit the bill if you are allowed to define new valid characters according to best practices.

tgv• 2 years ago

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

thriftwy4• 2 years ago

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

taejo2• 2 years ago

The Turing machine has a memory, it can absolutely cope with symbols meaning something different depending on what appears before them. The trouble is that it can't distinguish between infinitely many distinct symbols on the paper tape. Turing here shows that a human can't do that either, so that is not a way in which humans have more computational power than a Turing machine.

thriftwy4• 2 years ago

Not being to able to distinguish infinitely many symbols on a single tape does not mean there is a bound on the number of meanings that may be assigned to symbols.

k92mueller• 2 years ago

I have no idea about topology, so sorry if my question is stupid: Assume we are limited to the unit square (0<=x<=1 and 0<=y<=1). Now I map every real number in [0,1] to a symbol by simply defining the symbol for the number r as x=r and y=r. This results in a uncountable infinite amount of symbols. Now it's clearly not true that it's possible to describe any of those new symbols with a finite amount of symbols from a finite alphabet (because otherwise this would also be possible for real numbers). Where is my intuition wrong?

ainoobler8• 2 years ago

How can you tell the difference between (r,r) and (r+ε,r+ε)? The argument in the article assumes that there is an ε such that it is impossible to tell the difference between r and r+ε. So this means that the entire square can be covered by squares of side length ε and since the unit square is compact this means that there are only finitely many ε squares required to cover the entire unit square. Variation within the ε squares is imperceptible so this means there are only finitely many symbols that can be perceived to be different.

constantcrying• 2 years ago

we are limited to the unit square (0<=x<=1 and 0<=y<=1). Now I map every real number in [0,1] to a symbol by simply defining the symbol for the number r as x=r and y=r.

Every symbol has measure zero and so every symbol is identical.

kazinator3• 2 years ago

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.

schoen• 2 years ago

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!

fiforpg• 2 years ago

From a quick reading of the footnote, it seems that Turing uses optimal transport distance rather than the Hausdorff distance. Convergence in the latter implies convergence in the former, but not the other way round.

ridiculous_fish• 2 years ago

Why do we need the property that X is compact? Say we define X (the square) to exclude the boundary: X = (0,1)x(0,1). This is no longer a compact set, but it seems silly for the proof to now fail.

Is boundedness sufficient?

NotYourLawyer• 2 years ago

“Farthest” point doesn’t work if you drop compactness.

lzralbu• 2 years ago

Note that $A_k = \left[\frac{1}{k}, \frac{2}{k}\right] \times \left[\frac{1}{k}, \frac{2}{k}\right] \to \{(0, 0)\}$ in $[0,1]\times [0, 1]$ with the Hausdoff metric, so it is a Cauchy sequence in $X = (0,1) \times (0, 1)$ but without convergent subsequence, i.e., $F(X)$ is not complete, hence not compact so the finite subcover argument fails.

meroes• 2 years ago

Isn’t this just taking a common sense concept and adapting it to the concepts and language of Turing machines and also topology?

While yes it shows these are good tools, capable of confirming/proving these intuitions and showing exactly how these specific systems achieve that, is there ever any concern we are making too many redundant concepts? That may lead to confusion and obfuscate the search for novel ideas, which I think won’t always happen through said tools. It’s not like these kind of intuitions were on shaky grounds or could be disproven.

I wonder if anyone shares these opinions?

bmitc• 2 years ago

What is common sense about it?

is there ever any concern we are making too many redundant concepts

I need to read the contextual work, but I think it's actually the opposite here. Turing is a mathematician and is transferring a "foreign" notion into common mathematical concepts. It is a recasting of the concept so that it can be used. It isn't done just to do it.

citizen_friend• 2 years ago

Math is all about taking a notion from life that you might consider “common sense” and using it to solve a problem. You have to prove it works carefully though.

This is Turing’s works where he is translating the idea of a human “computer” into a mathematical machine.

lmm• 2 years ago

While yes it shows these are good tools, capable of confirming/proving these intuitions and showing exactly how these specific systems achieve that, is there ever any concern we are making too many redundant concepts? That may lead to confusion and obfuscate the search for novel ideas, which I think won’t always happen through said tools.

On the contrary, coming up with good general abstractions reduces the number of concepts you have to keep in your head and makes it much more possible to search for novel ideas. Imagine trying to figure out whether a given computing device was different to other computing devices without having the general concept of a Church-Turing computer - you wouldn't even get started.

trueismywork2• 2 years ago

These results help when you want to think about compression algorithms for example.

motohagiography• 2 years ago

non-anything question: Is this text/sheet an analogy for a thing's relationship to its substrate, or does the proof define a relationship or category of "thing-and-substrate?"

taejo2• 2 years ago

Turing's goal here is to justify why a Turing machine captures the "intuitive notion of a computation". To his audience, a "computer" is a person with a stack of paper and a pen, following an arbitrary procedure. Turing shows here that, even though a person can potentially draw infinitely many drawings on a sheet of paper, that doesn't give them any more computational power then writing symbols from a finite alphabet into a grid of squares.

The machine he introduces also writes symbols onto paper with a pen and reads them. So he really is talking about pens and sheets of paper, it's not an analogy for something else.

andybak• 2 years ago

I made a joke:

Prior to his seminal work Turing published a lesser known 1935 paper: "On Caffeine with an Application to the Anfangsverzögerungsproblem"

I think it might be a little too niche.

defrost• 2 years ago

The tapeworms that consumed your characters are still moving their heads backwards and forwards on whether to upvote, downvote, or move on.

It's impossible to say when they'll settle, so strap in for an indeterminate wait.

thih9• 2 years ago

We cannot tell at a glance whether 9999999999999999 and 999999999999999 are the same.

Off topic - some of us can, iOS underlines one of these for me, treating it as a phone number…

ithkuil• 2 years ago

BTW I noticed that the clickhouse CLI has an interesting visualization trick: wide numbers have each third digit rendered with an underline style. That's as effective as a thousands separator "," but you can copy paste the number into another program without having to edit the commas away

nyc1112• 2 years ago

Neither finite nor infinite is defined. I don't know what those words mean. So the assumption of an infinite alphabet doesn't make sense to me.

oefrha• 2 years ago

Finite and infinite are well defined in every set theory. You shouldn’t approach a topological proof without acquainting yourself with the most basic set theoretic foundation.

colinwilyb• 2 years ago

"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?

ycombinete• 2 years ago

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 endpoints", i.e., it includes all limiting values of points. For example, the open interval (0,1) would not be compact because it excludes the limiting values of 0 and 1, whereas the closed interval [0,1] would be compact.

tzs• 2 years ago

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| <= 1,

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

nimih• 2 years ago

Another way of stating this, which I think is rather non-obvious to people who have not studied some amount of pure math, is that technical mathematical definitions are almost never helpful absent a substantial amount of additional context, because their purpose is generally to capture and formalize a much more intuitively-understood idea or motivating phenomena. A professor of mine liked to joke that MathWorld was a website devoted to collecting definitions which were as technically correct as possible while also being useful to nobody[1], and I think the quoted wikipedia passage follows in that tradition beautifully.

[1] I don't know if this is still the case, but it certainly was in the late '00s.

nyc1112• 2 years ago

"In this paper Turing gives a topological argument that every written alphabet must be finite."

I searched Turing's paper and the word "alphabet" does not appear. I guess the author interprets Turing's use of "symbol" as an "alphabet". Can anyone familiar with Turing's paper clarify?

tasteslikenoise• 2 years ago

A different but to my taste more mathematically conventional way to make this argument would be instead to say that a symbol is a function from the square to [0, 1], that is, a grayscale image. A symbol, because of limitations of either its writer/printer or its reader/viewer, should have some "regularity": as you move around the image, there should be some quantitative restrictions on how rapidly the darkness of the gray color should change. In this kind of setup, the space of symbols is compact by a version of the Arzela-Ascoli theorem, which I think was fairly well-known by the time Turing was working. This also has the advantage of being straightforward to generalize to things like colored images by just changing [0, 1] to, say, [0, 1]^3 to represent RGB space, or whatever you want, as some others are mentioning in the comments.

As an aside, this is an interesting companion read:

"A pedagogical history of compactness" (https://arxiv.org/abs/1006.4131)

As a working mathematician, I can say that this kind of argument has become totally routine and, were I reading Turing's paper carefully, after seeing "epsilon" and "compact" I would think "makes sense" and move on. But, historically speaking, it's interesting to realize how recent the development of the abstract idea of compactness was when Turing was writing---the time between Frechet and Hausdorff's work on compactness (see the pedagogical history) and Turing is about the time between Google being founded and today.

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

Related Stories