5 ms·

You could easily turn a bug into a feature: add a couple of paragraphs to your post pointing out exactly this potential problem, and how you you could test to s

You could easily turn a bug into a feature: add a couple of paragraphs to your post pointing out exactly this potential problem, and how you you could test to see whether or not it really is a problem. Your post (which is already terrific) then becomes a great explanation of why not all functions work as one-way functions, and what it means for something to be a good one-way function.

jgrahamc 14y ago
Makes sense. I was aiming for a single 'a ha!' moment for the reader. What I actually want to do is so how well this mapping works with a real dictionary by writing some code to follow this algorithm with real words.
- 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 ago
    I 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.

jgrahamc 14y ago

Makes sense. I was aiming for a single 'a ha!' moment for the reader. What I actually want to do is so how well this mapping works with a real dictionary by writing some code to follow this algorithm with real words.

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