Complexity_ A Guided Tour - Melanie Mitchell [90]
I was disappointed, but not deterred. I managed to find Hofstadter’s phone number at the MIT AI Lab, and called several times. Each time the phone was answered by a secretary who told me that Hofstadter was not in, but she would be glad to leave a message. I left several messages but received no response.
Then, one night, I was lying in bed pondering what to do next, when a crazy idea hit me. All my calls to Hofstadter had been in the daytime, and he was never there. If he was never there during the day, then when was he there? It must be at night! It was 11:00 p.m., but I got up and dialed the familiar number. Hofstadter answered on the first ring.
He seemed to be in a much better mood than he was at the lecture. We chatted for a while, and he invited me to come by his office the next day to talk about how I could get involved in his group’s research. I showed up as requested, and we talked about Hofstadter’s current project—writing a computer program that could make analogies.
Sometimes, having the personality of a bulldog can pay off.
Simplifying Analogy
One of Hofstadter’s great intellectual gifts is the ability to take a complex problem and simplify it in such a way that it becomes easier to address but still retains its essence, the part that made it interesting in the first place. In this case, Hofstadter took the problem of analogy-making and created a microworld that retained many of the problem’s most interesting features. The microworld consists of analogies to be made between strings of letters.
For example, consider the following problem: if abc changes to abd, what is the analogous change to ijk? Most people describe the change as something like “Replace the rightmost letter by its alphabetic successor,” and answer ijl. But clearly there are many other possible answers, among them:
ijd (“Replace the rightmost letter by a d”—similar to Jake putting his socks “on”)
ijk (“Replace all c’s by d’s; there are no c’s in ijk ”), and
abd (“Replace any string by abd ”).
There are, of course, an infinity of other, even less plausible answers, such as ijxx (“Replace all c’s by d’s and each k by two x’s”), but almost everyone immediately views ijl as the best answer. This being an abstract domain with no practical consequences, I may not be able to convince you that ijl is a better answer than, say, ijd if you really believe the latter is better. However, it seems that humans have evolved in such a way as to make analogies in the real world that affect their survival and reproduction, and their analogy-making ability seems to carry over into abstract domains as well. This means that almost all of us will, at heart, agree that there is a certain level of abstraction that is “most appropriate,” and here it yields the answer ijl. Those people who truly believe that ijd is a better answer would probably, if alive during the Pleistocene, have been eaten by tigers, which explains why there are not many such people around today.
Here is a second problem: if abc changes to abd, what is the analogous change to iijjkk? The abc ⇒ abd change can again be described as “Replace the rightmost letter by its alphabetic successor,” but if this rule is applied literally to iijjkk it yields answer iijjkl, which doesn’t take into account the double-letter structure of iijjkk. Most people will answer iijjll, implicitly using the rule “Replace the rightmost group of letters by its alphabetic successor,” letting the concept letter of abc slip into the concept group of letters for iijjkk.
Another kind of conceptual slippage can be seen in the problem
abc ⇒ abd
kji ⇒ ?
A literal application of the rule “Replace the rightmost letter by its alphabetic successor” yields answer kjj, but this ignores the reverse structure of kji, in which the increasing alphabetic sequence goes from right to left rather than