Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

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

divisbyzero.com

Post reply on HN
Print view View original

31–40 of 120 posts

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

#31

Post by Smaug123 »

ainoobler wrote: post #19
Smaug123 wrote: post #13

Earlier quoted context omitted.

Assuming 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 be…

The universe is mathematical, all we can ever know about it is mathematical.

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

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

#32

Post by throwawayffffas »

ertgbnm wrote: post #12
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.

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.

The Planck length has been a thing since 1899.

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

#33

Post by thriftwy »

Smaug123 wrote: post #30
thriftwy wrote: post #27

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…

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

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.

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

#34

Post by Smaug123 »

thriftwy wrote: post #33
Smaug123 wrote: post #30

Earlier quoted context omitted.

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

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

You'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".

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

#35

Post by gus_massa »

Smaug123 wrote: post #11
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.

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.

The proof doesn't assume that they are formed by not-too-pathological penstrokes.

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

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.

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

#36

Post by perihelions »

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

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

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

#37

Post by kmoser »

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.

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

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

#38

Post by thriftwy »

Smaug123 wrote: post #34
thriftwy wrote: post #33

Earlier quoted context omitted.

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

You'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".

[flagged]

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

#39

Post by Smaug123 »

gus_massa wrote: post #35
Smaug123 wrote: post #11

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.

The proof doesn't assume that they are formed by not-too-pathological penstrokes. 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.) I think that every horrible-totally-pathological ink splash has a nice indistinguishable…

By "not-too-pathological" I intended at least to include the requirement "measurable".

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

#40

Post by codeflo »

kmoser wrote: post #37
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.

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?
Post reply on HN