Douglas Hofstadter's group is doing this work, and his book from last year
goes into it in detail.
I am skeptical about how well his results will generalize, although it is
an interesting class of problems. I can guarantee you that Hofstadter,
a very smart man, saw the answers to the problems above immediately.
In fact he and his students created the problems knowing they had these
clever answers. So then the task they faced was how to write a program
which would get the same answers that they got. That they were able to
do so is very impressive. But the question remains whether the data
structures they came up with are of general enough applicability that
they can shed light on other problems of AI.
Hal