Scribble, scribble, scribble

I suppose this is what they call a blog. Except that blogs are supposed to be updated more often than this is.

Feeds: Atom 1.0 (preferred), RSS 0.91. Front page: link.

< May 2007 >
   1 2 3 4 5
6 7 8 9101112
Wednesday 2007-05-09


It's curious the way things happen in parallel.

Case 1: Conway's "angel problem", open for for 25 years, suddenly seems to have been independently solved by four different people: András Máthé and Oddvar Kloster have proofs for an Angel of power 2, Brian Bowditch for an Angel of power 4, and Péter Gács for an angel of unspecified large power.

(Brief sketch of the problem: consider a game played by two players on an infinite chessboard. Play alternates. The first player has a single piece, called an Angel. On each move it can hop to a new square provided it doesn't move more than k units in either direction. The second player has an unlimited supply of pieces; on each move s/he places one of these pieces on any unoccupied square. The Angel isn't allowed to move to a square with a piece on. The first player wins if the Angel can keep moving for ever; the second player wins if s/he can box the Angel in. Who wins? Answer, it turns out: the Angel, even when k is as small as 2.)

The two strategies recently published for the Angel of power 2 are even very similar to one another: declare a connected region of the board (initially one half of it) unavailable, walk along its edge, and modify the region as squares get eaten. Perhaps the idea of this approach has been in the air for a while?

Case 2: within a couple of weeks of one another, two friends of mine independently make blog posts describing (or, in the latter case, referencing a Wikipedia description of) substantially the same programming technique and remark that it's a bit obscure and should be better known. The first happens to have a slightly more sophisticated version of the technique.

Edited, 2007-05-25, to fix a typo and to note:

Case 3: Cases 1 and 2 occurred at pretty much the same time. (I completely failed to notice this until a friend pointed it out.)

Case n+1: Cases 1, 2, ..., n occurred at pretty much the same time.