Turing's topological proof that every written alphabet is finite (2010) • Hacker News Board

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

#61

Post by bmitc » Tue, Jul 23, 2024, 10:23 PM UTC

meroes wrote: post #60

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, whic…

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.

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

#62

Post by contravariant » Tue, Jul 23, 2024, 10:59 PM UTC

andrewflnr wrote: post #58

nxobject wrote: post #3

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.

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 real…

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.

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

#63

Post by daedalus_j » Tue, Jul 23, 2024, 11:21 PM UTC

grvbck wrote: post #9

montecarl wrote: post #4

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.

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

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

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

#64

Post by andrewflnr » Tue, Jul 23, 2024, 11:52 PM UTC

contravariant wrote: post #62

andrewflnr wrote: post #58

Earlier quoted context omitted.

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 real…

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…

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

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

#65

Post by eru » Wed, Jul 24, 2024, 1:10 AM UTC

kragen wrote: post #17

ertgbnm wrote: post #12

Earlier quoted context omitted.

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.

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

If you want to use that sampling theorem, you have to bring up frequencies. Explaining those and how they apply to printer's ink is arguably more complicated than what Turing did; especially for his contemporary target audience.

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

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

#66

Post by citizen_friend » Wed, Jul 24, 2024, 2:22 AM UTC

meroes wrote: post #60

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, whic…

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.

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

#67

Post by kmoser » Wed, Jul 24, 2024, 2:47 AM UTC

codeflo wrote: post #40

kmoser wrote: post #37

Earlier quoted context omitted.

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…

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?

That's true if the time resolution is limited. Theoretically there could be no limit. It would not make for a very practical alphabet, but it would still be an unlimited alphabet.

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

#68

Post by lmm » Wed, Jul 24, 2024, 2:55 AM UTC

meroes wrote: post #60

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, whic…

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

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

#69

Post by motohagiography » Wed, Jul 24, 2024, 2:56 AM UTC

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

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

#70

Post by NotYourLawyer » Wed, Jul 24, 2024, 3:10 AM UTC

ridiculous_fish wrote: post #59

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?

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