[HN Gopher] Turing's topological proof that every written alphab...
___________________________________________________________________
Turing's topological proof that every written alphabet is finite
(2010)
Author : 082349872349872
Score : 42 points
Date : 2024-07-23 17:43 UTC (5 hours ago)
(HTM) web link (divisbyzero.com)
(TXT) w3m dump (divisbyzero.com)
| ainoobler wrote:
| Interesting 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 wrote:
| That's how the math works out in general unless you think some
| kind of soul exists.
| ainoobler wrote:
| It all follows from compactness so if the cognitive manifold
| is not compact then the conclusion is not true.
| andoando wrote:
| At 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 wrote:
| Is 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 wrote:
| I guess that means reincarnation is real.
| Smaug123 wrote:
| 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 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 wrote:
| If you are a mental clone but uncausally linked then is
| that still reincarnation?
| ainoobler wrote:
| The universe is mathematical, all we can ever know about
| it is mathematical.
| Smaug123 wrote:
| 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.
| throwaway43567 wrote:
| We do have
| https://en.m.wikipedia.org/wiki/Boltzmann_brain
|
| That may appear every (10^10)^50 years according to
|
| https://en.m.wikipedia.org/wiki/Timeline_of_the_far_futur
| e
| Y_Y wrote:
| But there may yet be more brain states than number of
| possible thoughts by the finite humans.
| Smaug123 wrote:
| Oh, 100%, it seems _extremely_ unlikely that multiple brain
| states in this sense don 't code for the same thought! If
| nothing else, you could only avoid that with an absurdly
| precise definition of "brain"; any practical definition of
| "brain" is very likely to include matter that is physically
| irrelevant to at least _some_ thoughts. I hedged with
| "1m^3" because the argument goes through even if you take
| the entire body to be the brain.
| tempfile wrote:
| Who 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 wrote:
| I made the obvious connection. It's an original thought from
| me and no one else.
| aiauthoritydev wrote:
| Well, this is true only if you think cognition and thought as a
| pure biological process totally dependent on state of brain.
| ainoobler wrote:
| I don't think that. I'm just explaining what follows
| logically if the cognitive manifold is compact.
| nxobject wrote:
| 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.
| montecarl wrote:
| 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.
| grvbck wrote:
| Next week on Show HN: I made a fractal font with unlimited
| scaling
| perihelions wrote:
| 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
| ashton314 wrote:
| This is a deep joke and hilarious. Thank you for sneaking
| in a Banach-Tarski reference here
| myhf wrote:
| assuming you are willing to spend an infinite amount of
| time doing the cutting
| kazinator wrote:
| The closed-form math formulas giving the glyphs of the font
| have to be written on a square piece of paper with limited
| resolution ...
| Smaug123 wrote:
| 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.
| Y_Y wrote:
| 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.
| gus_massa wrote:
| The proof doesn't assume that they are formed by not-too-
| pathological penstrokes.
|
| <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 e then they
| indistinguishable. (Where e 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.
| Smaug123 wrote:
| By "not-too-pathological" I intended at least to include
| the requirement "measurable".
| gus_massa wrote:
| I just notice that I used the wrong metric. The article
| uses the Hausdorf metric and I used the measure of the
| symetric difference.
|
| 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).
| ertgbnm wrote:
| 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.
| Y_Y wrote:
| Not far off though, "pix" was in use by at least 1932, and
| "pixel" by 1956[0].
|
| [0] https://en.wikipedia.org/wiki/Pixel
| kragen wrote:
| 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
| tempfile wrote:
| Approximating an arbitrary shape by covering it with tiny
| squares is not exactly new. The method of exhaustion goes
| back to 200BC.
| throwawayffffas wrote:
| The Planck length has been a thing since 1899.
| kmoser wrote:
| 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).
| codeflo wrote:
| If the observation time finite, and the time resolution of
| the observation is limited, then you'd still only have a
| finite number of symbols, wouldn't you?
| kazinator wrote:
| You also have to argue for finite color resolution, or else a
| color noise floor that masks the difference between similar
| colors.
|
| 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.)
| refulgentis wrote:
| Print resolution is far higher than 300 DPI, floor for the
| cheapest is 1000, most will do 4K. (not a correction, I am only
| sharing this because I think of this often because it seems
| leverage-able for something unique, and HN is a good place to
| share that sort of thing, in case someone is inspired)
| tempfile wrote:
| Turing'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 wrote:
| Convergent sequences are always Cauchy; for metric spaces,
| compactness and sequential compactness are the same.
| Smaug123 wrote:
| I 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 wrote:
| Yes and yes, but _conditional_ compactness is different, and
| Cauchy sequences are not always convergent. That 's why I
| mentioned completeness.
| thriftwy wrote:
| 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 VAZ,
| 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 wrote:
| 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".)
| thriftwy wrote:
| 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.
| Smaug123 wrote:
| 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".
| k92mueller wrote:
| I 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 wrote:
| How can you tell the difference between (r,r) and (r+e,r+e)?
| The argument in the article assumes that there is an e such
| that it is impossible to tell the difference between r and r+e.
| So this means that the entire square can be covered by squares
| of side length e and since the unit square is compact this
| means that there are only finitely many e squares required to
| cover the entire unit square. Variation within the e squares is
| imperceptible so this means there are only finitely many
| symbols that can be perceived to be different.
| kazinator wrote:
| > _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.
___________________________________________________________________
(page generated 2024-07-23 23:01 UTC)