4 ms·

If I understand this correctly (please correct me if I'm wrong) it would imply that one could encode an arbitrary number of bits by flipping only one bit on suc

If I understand this correctly (please correct me if I'm wrong) it would imply that one could encode an arbitrary number of bits by flipping only one bit on such a board with a random state, as long as the board is sufficiently large. You could for example encode book X by flipping one bit on some space, or a different book Y by flipping some other bit instead on another space on the exact same board, which is a fascinating thought to me. So if I take this description on orders of magnitude from Wikipedia: "5 000 000 bits – Typical English book volume in plain text format of 500 pages × 2000 characters per page and 5-bits per character." This would mean that the board would need to have a size of 2^5000000 spaces to successfully do this for texts of up to 500 pages x 2000 chars per page.

Chinjut 12y ago
Sure. This doesn't seem so surprising to me; after all, the number of possible answers you may choose from for the question "Which bit do you want to flip?" is precisely the same as the number of possible answers you may choose from for the question "Which book do you want to specify?". (That's not a proof of sufficiency, mind you (the proof is the construction of the appropriate Hamming code). It's just reason to not find the result particularly counterintuitive.)
schoen 12y ago
It's kind of like a counterpart to Martin Gardner's amazing observation in aha! Gotcha that you can store books with a single mark on a stick (assuming you can measure tiny distances with superhuman accuracy): http://board.flatassembler.net/topic.php?t=16574 http://board.flatassembler.net/topic.php?t=16574 It's not physically realizable: people in that particular comment thread point out problems about the size of an atom, but there's also the Planck length, which I believe people theorize is in some sense a minimum size for objects in our universe, and I calculated that there are only around 2¹¹⁶ of them in a meter, so you could only store 116 bits by making a single Planck length-sized mark on a meter stick. :-( :-( But it's a super-cool idea!
- tunesmith 12y ago
  Wasn't there some project about trying to find the independent bits of information among all the people in the world? So that if you answered a 33-question (2^33 is about 8.5 billion) true/false survey, your answers would be distinct from anyone else's. Well I guess you could do it with longitude, latitude, and timestamp of birth, but I think it was supposed to be a personality survey.
  - schoen 12y ago
    Arvind Narayanan has made this observation in terms of the difficulty or impossibilities of anonymizing databases: http://33bits.org/ http://33bits.org/ However, he didn't propose a particular list of 33 questions whose answers are maximally statistically independent. Even with things that are totally uncorrelated, you do get some chance overlap where people happen to have the same answers on a small number of them. For example, if we took the first 33 bits of the SHA256 of one's HN username, you and I happen to agree in positions 7, 8, 11, 13, 15, 17, 18, 19, 21, 26, 27, 28, 29, 31, and 32. (So we could say that each additional bit of that SHA256 value doesn't actually provide a full additional bit of distinguishing power relative to the previous ones.)

Chinjut 12y ago

Sure. This doesn't seem so surprising to me; after all, the number of possible answers you may choose from for the question "Which bit do you want to flip?" is precisely the same as the number of possible answers you may choose from for the question "Which book do you want to specify?". (That's not a proof of sufficiency, mind you (the proof is the construction of the appropriate Hamming code). It's just reason to not find the result particularly counterintuitive.)

schoen 12y ago

It's kind of like a counterpart to Martin Gardner's amazing observation in aha! Gotcha that you can store books with a single mark on a stick (assuming you can measure tiny distances with superhuman accuracy): http://board.flatassembler.net/topic.php?t=16574 http://board.flatassembler.net/topic.php?t=16574 It's not physically realizable: people in that particular comment thread point out problems about the size of an atom, but there's also the Planck length, which I believe people theorize is in some sense a minimum size for objects in our universe, and I calculated that there are only around 2¹¹⁶ of them in a meter, so you could only store 116 bits by making a single Planck length-sized mark on a meter stick. :-( :-( But it's a super-cool idea!

tunesmith 12y ago
Wasn't there some project about trying to find the independent bits of information among all the people in the world? So that if you answered a 33-question (2^33 is about 8.5 billion) true/false survey, your answers would be distinct from anyone else's. Well I guess you could do it with longitude, latitude, and timestamp of birth, but I think it was supposed to be a personality survey.
- schoen 12y ago
  Arvind Narayanan has made this observation in terms of the difficulty or impossibilities of anonymizing databases: http://33bits.org/ http://33bits.org/ However, he didn't propose a particular list of 33 questions whose answers are maximally statistically independent. Even with things that are totally uncorrelated, you do get some chance overlap where people happen to have the same answers on a small number of them. For example, if we took the first 33 bits of the SHA256 of one's HN username, you and I happen to agree in positions 7, 8, 11, 13, 15, 17, 18, 19, 21, 26, 27, 28, 29, 31, and 32. (So we could say that each additional bit of that SHA256 value doesn't actually provide a full additional bit of distinguishing power relative to the previous ones.)