3 ms·
Here's a rough draft that would, I think, only reinforce the 'aha' moment. It could be inserted as the third last paragraph: "There's a potential problem with
by michael_nielsen 14y ago
Here's a rough draft that would, I think, only reinforce the 'aha' moment. It could be inserted as the third last paragraph:
"There's a potential problem with this procedure. What if Alice had started with some other word - say 'FILES' - and following this procedure also led to the word 'THINGS'. In fact, it might be that many, many English words all lead to the word 'THINGS'. If that were so then Bob would be justified in feeling skeptical that Alice had solved the crossword. She'd be using a "bad" one-way function. Both Alice and Bob need to be confident that this procedure doesn't lead to too many collision between English words. This is a challenge that needs to be addressed if you want to prove that a function is truly a good one-way function."
- Someone 14y agoI think it is highly likely that many words clash that way. Worse, I expect many clashes between words that fit the crossword description. Consider, for example, a description of 'animal'. Now, look up a few animal: http://www.merriam-webster.com/dictionary/elephant http://www.merriam-webster.com/dictionary/elephant: any of a family (Elephantidae, the elephant family) of... http://www.merriam-webster.com/dictionary/rhinoceros http://www.merriam-webster.com/dictionary/rhinoceros: any of a family (Rhinocerotidae) of... http://www.merriam-webster.com/dictionary/crocodile http://www.merriam-webster.com/dictionary/crocodile: any of several large... http://www.merriam-webster.com/dictionary/buffalo http://www.merriam-webster.com/dictionary/buffalo: any of several wild bovids... So, there is some variation, but it isn't hard to find immediate collisions, especially for related words. That makes sense; a dictionary should not attempt to vary the way it describes similar words.