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

71–80 of 120 posts

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

#71

Post by snthpy »

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.

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?

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

#72

Post by snthpy »

snthpy wrote: post #71
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.

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?

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

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

#73

Post by snthpy »

snthpy wrote: post #72
snthpy wrote: post #71

Earlier quoted context omitted.

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?

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

Ignore me. That's no different to having infinite length strings with a finite alphabet.

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

#74

Post by kragen »

eru wrote: post #65
kragen wrote: post #17

Earlier quoted context omitted.

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

fair point

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

#75

Post by tempfile »

perihelions wrote: post #36
grvbck wrote: post #9

Earlier quoted context omitted.

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

Turing actually addressed this in his argument!

> If these sets are restricted to be measurable

measurable sets are not Banach-Tarski-able :)

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

#77

Post by flir »

daedalus_j wrote: post #63
grvbck wrote: post #9

Earlier quoted context omitted.

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

This reminds me of a design for analogue TV from the late 80s/early 90s. Instead of the electron gun scanning in horizontal lines, it follows a space-filling, non-crossing, self-similar curve. Want to upgrade the resolution? Just build a TV that renders the curve one generation deeper, and stuff more data into the analogue broadcast signal. Older TVs can still render the new signal, maybe with a slightly higher noise floor.

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

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

#78

Post by dinkelberg »

Y_Y wrote: post #14
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.

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.

Why should it not allow for your spiralling brushstroke? You can divide the spiral into the strokes corresponding to each turn around the center. We can assume that each of these strokes is measurable (otherwise we would not need the construction of the spiral). Then the entire spiral is just a countable union of those measurable strokes, thus it is measurable itself.

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

#79

Post by defrost »

andybak wrote: post #76

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.

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.

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

#80

Post by taejo »

motohagiography wrote: post #69

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

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.

Post reply on HN