4 ms·

Reminds me an argument about crossword puzzles I think comes from Shannon. It goes like this: in a sufficiently "fault-tolerant" language (ie with low per-char

by cscheid 13y ago

Reminds me an argument about crossword puzzles I think comes from Shannon. It goes like this: in a sufficiently "fault-tolerant" language (ie with low per-character information content, which sorta gives large Hamming distance), crosswords become impossible, because puzzles won't be satisfiable: words could never line up right. But in a sufficiently compact language (many bits per character in words, and Hamming distance thus tending towards zero), crosswords are impossible as well, but now because puzzles would be ambiguous: too many words that fit. Somehow, natural languages appear to fit somewhere in the middle.

cbr 13y ago
in a sufficiently compact language crosswords are impossible as well, but now because puzzles would be ambiguous: too many words that fit This ignores the clues, which restrict which words are acceptable in a space. While the clues are mostly there to make the puzzle easier, resolving ambiguity is a secondary purpose.
- cscheid 13y ago
  So I looked it up, and it's actually on the seminal 1948 paper: http://cm.bell-labs.com/cm/ms/what/shannonday/shannon1948.pdf http://cm.bell-labs.com/cm/ms/what/shannonday/shannon1948.pd... It turns out that I either hallucinated (incorrectly, perhaps) one side of the argument, or I read it from some other place, because the paper only talks about one side, the one about feasibility. The relevant paragraph follows: "The redundancy of a language is related to the existence of crossword puzzles. If the redundancy is zero any sequence of letters is a reasonable text in the language and any two-dimensional array of letters forms a crossword puzzle. If the redundancy is too high the language imposes too many constraints for large crossword puzzles to be possible. A more detailed analysis shows that if we assume the constraints imposed by the language are of a rather chaotic and random nature, large crossword puzzles are just possible when the redundancy is 50%. If the redundancy is 33%, three-dimensional crossword puzzles should be possible, etc." Anyway, to somewhat rescue a botched story, the ambiguity part reminds me of the mindblowingly awesome and famous puzzle by Jeremiah Ferrell on the eve of the 1996 presidential election, which clue was "Lead story in tomorrow's paper", with possible answers BOBDOLE ELECTED or CLINTON ELECTED, both satisfying all crossclues as well! Amazing: http://cdn0.dailydot.com/uploaded/images/original/2013/2/12/nytimescrossword.jpg http://cdn0.dailydot.com/uploaded/images/original/2013/2/12/...
kpreid 13y ago
> Somehow, natural languages appear to fit somewhere in the middle. I don't recall where, but I have heard an argument that there is pressure on the information density of natural language, as follows: If you are frequently misunderstood, then you can save effort (not have to repeat/explain) by adding redundancy. If you are never misunderstood, then you can save effort by removing redundancy. There's no particular reason the result of this process should be good for crosswords, but it's a reason to be in the middle rather than at the extremes.
- lutusp 13y ago
  > If you are frequently misunderstood, then you can save effort (not have to repeat/explain) by adding redundancy. If the added words improve comprehension, then they're not redundant. Not all repetition is redundant. Oh, by the way, did I forget to mention that not all repetition is redundant? :)

by cscheid 13y ago

cbr 13y ago

in a sufficiently compact language crosswords are impossible as well, but now because puzzles would be ambiguous: too many words that fit This ignores the clues, which restrict which words are acceptable in a space. While the clues are mostly there to make the puzzle easier, resolving ambiguity is a secondary purpose.

cscheid 13y ago
So I looked it up, and it's actually on the seminal 1948 paper: http://cm.bell-labs.com/cm/ms/what/shannonday/shannon1948.pdf http://cm.bell-labs.com/cm/ms/what/shannonday/shannon1948.pd... It turns out that I either hallucinated (incorrectly, perhaps) one side of the argument, or I read it from some other place, because the paper only talks about one side, the one about feasibility. The relevant paragraph follows: "The redundancy of a language is related to the existence of crossword puzzles. If the redundancy is zero any sequence of letters is a reasonable text in the language and any two-dimensional array of letters forms a crossword puzzle. If the redundancy is too high the language imposes too many constraints for large crossword puzzles to be possible. A more detailed analysis shows that if we assume the constraints imposed by the language are of a rather chaotic and random nature, large crossword puzzles are just possible when the redundancy is 50%. If the redundancy is 33%, three-dimensional crossword puzzles should be possible, etc." Anyway, to somewhat rescue a botched story, the ambiguity part reminds me of the mindblowingly awesome and famous puzzle by Jeremiah Ferrell on the eve of the 1996 presidential election, which clue was "Lead story in tomorrow's paper", with possible answers BOBDOLE ELECTED or CLINTON ELECTED, both satisfying all crossclues as well! Amazing: http://cdn0.dailydot.com/uploaded/images/original/2013/2/12/nytimescrossword.jpg http://cdn0.dailydot.com/uploaded/images/original/2013/2/12/...

kpreid 13y ago

> Somehow, natural languages appear to fit somewhere in the middle. I don't recall where, but I have heard an argument that there is pressure on the information density of natural language, as follows: If you are frequently misunderstood, then you can save effort (not have to repeat/explain) by adding redundancy. If you are never misunderstood, then you can save effort by removing redundancy. There's no particular reason the result of this process should be good for crosswords, but it's a reason to be in the middle rather than at the extremes.

lutusp 13y ago
> If you are frequently misunderstood, then you can save effort (not have to repeat/explain) by adding redundancy. If the added words improve comprehension, then they're not redundant. Not all repetition is redundant. Oh, by the way, did I forget to mention that not all repetition is redundant? :)