Essay Review: To Seek Whence Cometh a Sequence

Listen to the beginning of the prelude of the sixth cello suite by Bach, and you’ll notice something interesting. (Here is a performance by Mischa Maisky.) The first few notes are as follows: D-D-D-D-D-F#-D-D-A-D-D-D(up one octave). So, it starts with five consecutive D’s. Still, when we listen to this music, it’s clear that the D’s are not all the same. The notes come in three-note blocks; in each of these blocks, the first two notes are D’s, and the last note is part of a D major arpeggio. But, it just so happens that the first note in the arpeggio is the same as the previous note. It doesn’t require any significant musical knowledge in order to understand the outline of the pattern. But how is it that we can figure out what’s going on so easily?
If you’re a little bit more attentive when you watch the video of the prelude of the sixth cello suite, you’ll notice something else that’s interesting. The first two notes are played with one bow, but then future notes are played in groups of three, as follows: (D-D) (D-D-D) (F#-D-D) (A-D-D) (D (up one octive) etc.). So, the first block in this grouping has two notes, and the future ones have three. Thus, there is an initial glitch in the sequence. Of course, Maisky could have chosen to group the notes differently so as to avoid the glitch, but he didn’t. He felt that there was something else that was more important than arranging for the initial string of the sequence to look like the rest of it. One can conjecture about what else he felt was more important, but I won’t do that here.
Let’s look at some number sequences and see how we can interpret them. Consider the sequence 1,2,2,3,3,4,4,5,5,6,6,7,… Our initial reaction to this sequence is probably that it should be interpreted as (1) (2,2) (3,3) (4,4) (5,5) (6,6) (7,7) etc. But this grouping has a glitch at the beginning: the first block has only a single number in it, and all the rest of the blocks have two numbers. Perhaps we shouldn’t be considering this sequence at all but rather a slightly different one, with an extra 1 at the beginning?
Well, no. The sequence is right; the grouping is wrong. It "should" be interpreted as (1,2) (2,3) (3,4) (4,5) (5,6) etc. That way, all the blocks look analogous, and there’s no initial glitch. Still, we have a natural tendency to put the repeated numbers in the same block; intuitively, that feels more natural than putting the rising sequences in the same block and breaking the consecutive occurrences of the same number apart. So, again, there’s a trade-off: do we prefer to group them as (1) (2,2) (3,3) etc., which looks more aesthetically pleasing but has an initial glitch, or do we prefer to group them as (1,2) (2,3) (3,4) etc., which avoids the glitch but feels slightly less natural?
Let’s now ask the question that is that subject of Hofstadter’s essay "To Seek Whence Cometh a Sequence." Given the first several terms of a sequence, how do we recognize which sequence it’s part of? How do we know what the next term is supposed to be?
When I was in high school, these questions annoyed me. There’s no way I can tell, my logic went, what comes next; I can turn an initial string into any sequence I want; in fact, I can even fit a polynomial whose next value is anything I want to the initial string. Hofstadter gives the following playful example of this sort of behavior. He asks: What’s the next term in the sequence beginning 0, 1, 2? If you said 3, you didn’t understand the sequence; clearly, the next term is 720!. Why? Well, the zeroth term is 0, followed by no factorials. The first term is 1, followed by one factorial. The second term is 2, followed by two factorials. So, naturally, the third term is 3, followed by three factorials, which is 720!.
So, that was all very clever, but let’s stop for a moment and look at what happened there. What numbers did I have to think about in order to understand this sequence? The numbers I wrote down in order to describe it were 0, 1, 2, 3; each of those numbers occurred twice (zero with zero factorials, one with one factorial, and so forth). So, in order for the sequence Hofstadter gives to make sense, we’ve already admitted to ourselves that 0, 1, 2, 3 is a better fit for the sequence than 0, 1, 2, 720!. We really have to be obstinate in order to ignore our natural impulses and find something more complicated.
Hofstadter claims that many mathematicians are not fond of these "continue the pattern" games, for the reason I mentioned above. But, he neglects to mention something I find really obvious: mathematicians don’t want to play these games as a sort of defense mechanism. We’re supposed to be really good at finding patterns and understanding them; it’s a blow to our confidence if a nonmathematician asks us what the pattern is, and we can’t find it. So, we hide behind our theorems.
Hofstadter also discusses what it means to understand a sequence. There are at least two parts to this. If we understand a sequence, we should be able to find more terms of it given an initial string, but also, we should be able to find other sequences that follow related rules. Consider the sequence 2,2,2,3,3,2,2,2,3,3,2,2,2,3,3,… If you’re only interested in finding more terms, you can say that the sequence is 5-periodic, and so to find the next term, we just have to look back five terms and copy that number. But this sequence is "about" more than just being 5-periodic. I don’t think the sequence 1,2,3,6,8,1,2,3,6,8,1,2,3,6,8,… is really a generalization of the given sequence. But, neither is 1,1,1,2,2,1,1,1,2,2,1,1,1,2,2,… No; the given sequence is "about" duality: there are three twos, followed by two threes. One of its blocks (2,2,2,3,3) is analogous to a block consisting of the work "blue" in red ink, followed by the word "red" in blue ink. Alternatively, if we want to go back to numbers, we could say that the given sequence is analogous to the sequence 1,1,1,1,1,5,1,1,1,1,1,5,1,1,1,1,1,5,… Stealing a term from music, Hofstadter calls the given sequence "hemiolic."
Hofstadter is interested not just in understanding how we interpret sequences, but also in programming computers in order to do so. (The name "Seek Whence" is the name of a computer program that does this, built by one of his students. Of course, it’s also a classic example of a Hofstadterian play on words.) When writing AI programs like this one, the ideal solution is to be able to understand human reasoning at a sufficiently deep level, so as to get the computer to emulate it. But, is it so bad to ask the computer to use reasoning that is not comparable to what a human would do?
One possible approach a computer might take in order to solve the sequence problem would be to try to write out a lot of formulae that generate the initial string handed to it, and see which one is the shortest. The logic behind this, if any, is that the shortest formula should be the one that seems the most natural. This would take a long time for a computer, even with great processing capacity, but at least it’s a potential approach. Unfortunately, I don’t think it’s going to get the right answer very often using this approach: we can fit polynomials to any finite data set; it doesn’t take that many characters to write down a polynomial, even of fairly high degree. Will the program find a "random" polynomial too frequently using this approach? I don’t have enough intuition about this to tell, but I think that striving for short solutions could be at least some part of a good solution, albeit one relatively far away from any human approach.
In other situations, we have been successful in designing something like AI but in a manner not parallel to that of human thought. In particular, we have been very successful at designing computer programs to play chess well. But while they accomplish the same goal as humans do, they go about it in a very different way. Humans tend to have a lot of board feel and intuition when playing chess; we don’t come to our conclusions by calculating billions of sample lines and giving each line a numerical score. But computers do. It’s rather amazing that we can program computers to do what we know how to do largely through intuition and experience, by sheer calculation.
If the goal of AI is to learn more about how humans think, then chess-playing computer programs probably won’t help much; their analysis procedure is so far removed from our own, and we have nowhere near the computational capabilities needed to make the computer approach to chess work in our own heads. Yet, we can learn a lot about playing chess from analyzing with computers. In fact, through analyzing with computers, humans start to think in a more computer-ish manner about chess. I can talk about a chess game with a similarly serious player and say something like "I think this position is -0.7," and I’d expect em to understand what that means. And our play starts to emulate that of the computer as well. Before computers became an essential tool for chess study at the top level, games between top grandmasters were largely based on chess principles. Now, they tend to be based far more on concrete lines: if you can’t find an explicit variation to refute your idea, then you’re doing well!

As with Hofstadter’s other writings, this essay is filled with exciting ideas and silly word play, which makes it fun to read. It’s not Gödel, Escher, Bach, but it’s an interesting piece. It’s also only the first chapter of a book, called Fluid Concepts and Creative Analogies. After reading various serious books (Eating Animals, Anmal Equality, and What Becomes You), it’s nice for me to return home and read a nerd book again. It serves to remind me that that’s the world I really live in. I look forward to reading the rest of the book.


About Simon

Hi. I'm Simon Rubinstein-Salzedo. I'm a mathematics postdoc at Dartmouth College. I'm also a musician; I play piano and cello, and I also sometimes compose music and study musicology. I also like to play chess and write calligraphy. This blog is a catalogue of some of my thoughts. I write them down so that I understand them better. But sometimes other people find them interesting as well, so I happily share them with my small corner of the world.
This entry was posted in AI, book reviews, numbers. Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s