17 ms·
Turing's topological proof that every written alphabet is finite (2010)
- ainoobler 2y agoInteresting 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 2y agoThat's how the math works out in general unless you think some kind of soul exists.
- ainoobler 2y agoIt all follows from compactness so if the cognitive manifold is not compact then the conclusion is not true.
- andoando 2y agoAt 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
- Smaug123 2y agoIs 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.
- ainoobler 2y agoI guess that means reincarnation is real.
- Smaug123 2y agoAssuming you're not trolling: nope, that would be an empirical question of how many brain states ever actually arise in the world during the time humans exist, and how much space and time it takes to maintain a given brain state. The universe is currently expected to stop being able to support human life at some point in the future, so the pigeonhole principle argument requires some physical parameters to be known before you can apply it; and even if the pigeonhole principle did apply, you still can't know by that argument whether any given brain-state is repeated (and if so, how many times). Things which you can deduce using only mathematics, and no physical data, are necessarily extremely weak statements about reality.
- Y_Y 2y agoIf you are a mental clone but uncausally linked then is that still reincarnation?
- ainoobler 2y agoThe universe is mathematical, all we can ever know about it is mathematical.
- Smaug123 2y agoA very strong empirical statement about the nature of reality, and a strong statement about the nature of mathematics, neither of which everyone agrees with! (What will your reply be if we discover a halting oracle at the centre of the galaxy? Mathematics doesn't forbid that: the Church-Turing thesis is an empirical statement, and it's the empirical scientific law of induction which is what tells us that we're extremely unlikely to find a halting oracle.) 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.
- tempfile 2y agoWho 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.
- ainoobler 2y agoI made the obvious connection. It's an original thought from me and no one else.
- aiauthoritydev 2y agoWell, this is true only if you think cognition and thought as a pure biological process totally dependent on state of brain.
- ainoobler 2y agoI don't think that. I'm just explaining what follows logically if the cognitive manifold is compact.
- nairboon 2y agoWhat exactly do you mean with "cognitive manifold"?
- ainoobler 2y agoIt's a made up concept and it includes all possible ways people can think anything. If you want something concrete then you can consider sheaves of finitely presented algebras on the nervous system considered as a topological space with the obvious covering relations, continuous transformations, and algebra morphisms.
- deleted 2y ago[deleted]
- nxobject 2y agoJust 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.
- andrewflnr 2y agoI'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 2y agoI 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.
- andrewflnr 2y ago> 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. 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.
- montecarl 2y agoIt 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 2y agoNext week on Show HN: I made a fractal font with unlimited scaling
- perihelions 2y agoYou 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
- ashton314 2y agoThis is a deep joke and hilarious. Thank you for sneaking in a Banach-Tarski reference here
- myhf 2y agoassuming you are willing to spend an infinite amount of time doing the cutting
- byteknight 2y agoI smell a supertask
- tempfile 2y agoTuring actually addressed this in his argument! > If these sets are restricted to be measurable measurable sets are not Banach-Tarski-able :)
- kazinator 2y ago
- tempfile 2y agoTuring'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 2y agoConvergent sequences are always Cauchy; for metric spaces, compactness and sequential compactness are the same.
- Smaug123 2y agoI 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.)
- tempfile 2y agoYes and yes, but conditional compactness is different, and Cauchy sequences are not always convergent. That's why I mentioned completeness.
- bubblyworld 2y agoGiven 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.
- 2y ago
- thriftwy 2y agoI 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.
- Smaug123 2y agoOf 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".)
- thriftwy 2y agoI'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.
- Smaug123 2y agoYou're talking entirely about the meaning of symbols, right. That's not a question Turing addressed at all, and the answer is trivially "there are infinitely many possible semantics". Turing only addressed the question of how many physically distinct symbols there could be, and came up with the result "finitely many".
- k92mueller 2y agoI 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?
- ainoobler 2y agoHow 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 2y 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.
- kazinator 2y 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 2y agoI 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 2y agoFrom 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.
- meroes 2y agoIsn’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 2y agoWhat 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 2y agoMath 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 2y 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.
- trueismywork 2y ago
- ridiculous_fish 2y agoWhy 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 2y ago“Farthest” point doesn’t work if you drop compactness.
- lzralbu 2y agoNote 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.
- motohagiography 2y agonon-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?"
- taejo 2y agoTuring'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 2y agoI 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 2y agoThe 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 2y 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 2y agoBTW 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
- nyc111 2y agoNeither 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 2y agoFinite 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 2y 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 2y agoThe 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 2y agoI'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_numbers_and_transcendence https://en.wikipedia.org/wiki/Liouville_number#Liouville_num...
- nyc111 2y 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?
- gssa 2y ago[flagged]
- tasteslikenoise 2y agoA 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 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.