Turing's topological proof that every written alphabet is finite (2010)
divisbyzero.com
divisbyzero.com
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.
> If these sets are restricted to be measurable
measurable sets are not Banach-Tarski-able :)
(Anyone know what I'm talking about? I assume it was obsoleted by digital solutions, but I'd like to know if there were any serious flaws in the design).
Ah! Found this: https://www.ripcorddesigns.com/blog-news/who-needs-rastas-an... - there's even a patent! I was searching on space-filling curve, not Hilbert curve.
Perhaps the sense of "I" can be that base, which then allows the expansion of I, I, I (sense of I around I) which expands to in front, behind, etc.
:-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.)
My topology is rusty and I don't genuinely doubt the validity of the argument, but I'm having fun trying to poke holes.
<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.
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).
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).
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.
Related :
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.
The argument from pixels is more natural to us these days, that's why we think it's simpler.
(I had similar reactions to many other older style proofs when I was studying math.)
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.)
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?
[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.
https://www.hypebot.com/hypebot/2020/02/every-possible-melod...
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.
Off topic - some of us can, iOS underlines one of these for me, treating it as a phone number…
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.
Well yeah, I only brought that up to try to steelman the comment I was responding to.
> 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.
That's all explicitly covered in the article. In particular, not having details too small to see is basically the definition of an alphabet for the purposes of the theorem. And as soon as you're using "numbers", you aren't really using an "infinite alphabet", you're using whichever numeral system with an extra layer of interpretation. Turing separately covered the case of simulating an infinite alphabet with countably infinite strings in a finite alphabet.
Ed: clarity.
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.
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?
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.
[1] I don't know if this is still the case, but it certainly was in the late '00s.
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
> The proof of this is quite straightforward. Suppose a is a real root of an irreducible equation
f(x) = a0 x^v + ... + av = 0,
|f(p/q)| = |a-p/q| |f'(z)| >= 1/q^v; z = a + t(p/q-a),
|t| <= 1,
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...
Automated theorem proverbs can probably solve this problem though..
I had a professor who derived Riemann metric from just area of triangle and limits over the course of a semester. So I see what you're getting at, but such books will probably he too long for most people to read anyway.
> 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.)
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 =)
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?
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.
This is Turing’s works where he is translating the idea of a human “computer” into a mathematical machine.
> 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.
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.
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.
That may appear every (10^10)^50 years according to
But you've missed the point: even assuming that mathematics can perfectly model the universe, you cannot use weak physical hypotheses ("human brains are finite, there is an injection from human mind-states into human brains") and fully general mathematics (the pigeonhole principle) to derive such specific strong truths as "a particular human mind-state is repeated in a predictable way in the universe". You can at best derive general truths such as "at least one human mind-state is repeated at least once, somewhere", if the universe happens to have its physical parameters set in such a way that the pigeonhole principle holds.
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
Is boundedness sufficient?
Every symbol has measure zero and so every symbol is identical.
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?
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.
> 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.
It's impossible to say when they'll settle, so strap in for an indeterminate wait.