The Angel Problem has been Solved! (Maybe)
Forget computing the Kazhdan-Lusztig polynomials for E8, a far more important theorem has apparently been proved. I won't state the answer here as it's fun to think about the problem for yourself. But a number of proposed proofs of solutions to the Angel problem have been informally published, at least electronically.
Firstly, what is the problem? Wikipdia has a succinct write up. But here's a quick summary anyway:
The game of Angels and Devils, invented by John Conway (the same Conway as in the Game of Life, the Monstrous Moonshine conjectures, the proof that subatomic particles have free will and so on), is played on an infinite chessboard. Fix some constant k. One player plays the Angel. The other plays the Devil. On the Devil's turn, he may eat one square on the chessboard. (The devil doesn't actually have a piece, he just eats whatever square he wants.). On the Angel's turn she jumps to a square (distinct from the current one) up to k king's moves away. The Devil wins if the Angel has no legal move. The Angel wins if she has a strategy that guarantees always to have a legal move. For each k, who wins? Until recently it was unknown if the Angel could win even for arbitrarily large k. This may seem like a surprise, after all, if the angel can move 1,000 king's moves, surely she can easily evade the jaws of the devil who can only chomp one square at a time. But surprisingly, the obvious Angel strategies that come to mind can be countered.
What's nice about this problem is that it's so easy to state, and yet has stumped some of the smartest people who like to think about these problems.
Two papers with possible solutions are Máthé's and Kloster's. I don't think either of them have formally been published yet so I don't know if the peer review is complete.
Firstly, what is the problem? Wikipdia has a succinct write up. But here's a quick summary anyway:
The game of Angels and Devils, invented by John Conway (the same Conway as in the Game of Life, the Monstrous Moonshine conjectures, the proof that subatomic particles have free will and so on), is played on an infinite chessboard. Fix some constant k. One player plays the Angel. The other plays the Devil. On the Devil's turn, he may eat one square on the chessboard. (The devil doesn't actually have a piece, he just eats whatever square he wants.). On the Angel's turn she jumps to a square (distinct from the current one) up to k king's moves away. The Devil wins if the Angel has no legal move. The Angel wins if she has a strategy that guarantees always to have a legal move. For each k, who wins? Until recently it was unknown if the Angel could win even for arbitrarily large k. This may seem like a surprise, after all, if the angel can move 1,000 king's moves, surely she can easily evade the jaws of the devil who can only chomp one square at a time. But surprisingly, the obvious Angel strategies that come to mind can be countered.
What's nice about this problem is that it's so easy to state, and yet has stumped some of the smartest people who like to think about these problems.
Two papers with possible solutions are Máthé's and Kloster's. I don't think either of them have formally been published yet so I don't know if the peer review is complete.
posted by sigfpe at Wednesday, March 21, 2007
11 Comments:
That "free will theorem" stuff really bothers me - the result was about determinism, not free will (unless you define free will to be a purely theoretical term, rather than the ordinary term that people care about). It just states that if experimenters don't behave deterministically, then at least some particles don't either - which really seems quite unsurprising when you think about it. It's only when you equate indeterminism and free will that it sounds surprising (and philosophically interesting). But this question of what relation free will has to determinism is perhaps the central question in the philosophical literature on free will - and while many people argue that free will implies indeterminism and many deny it, I don't think anyone claims that indeterminism implies free will (in the sense that people care about it).
Saying that this theorem means that electrons have free will is almost like saying that the discovery of the T quark was the culmination of the search for Truth.
Kenny,
Of course I was being delberately provocative in my one phrase summary of the Conway-Kochen result, as that is more likely to provoke people to read and think about it.
> It just states that if experimenters don't behave deterministically, then at least some particles don't either - which really seems quite unsurprising when you think about it
The thing that is "quite unsurprising when you think about it" surely isn't the same thing as what the Conway-Kochen theorem proves because the thing that is "quite unsurprising when you think about it" wouldn't essentially require results from quantum mechanics in its proof.
A far more important theorem has been disproved :-)
Let's wait and see what the professionals have to say about it : http://arxiv.org/abs/math.NT/0703367
Wow, I spent a lot of time thinking about the angel problem back in college! It will be fun to read these papers.
I was being a bit deliberatively provocative in my comment as well.
Of course, just because something isn't too surprising when you think about it doesn't mean that it's not hard or interesting to prove. The Jordan curve theorem is also unsurprising when you think about it, but makes essential use of some fundamental facts in real analysis. But there's also a good chance that I'm misinterpreting the brief summary of the actual mathematical content that I've seen.
I just think that they tend to oversell it with the title they've given the result.
Máthé writes early in his paper that if the angel can go arbitrarily far, it must have an infinite strategy by taking “a suitable limit” of the strategies. Since the players have uncountably many strategies, I'm not sure this is true. Can someone fill in the argument for me?
How can the Angel ever win, if his only goal in winning is to continue forever? YOu never win if the game never ends :-D
Anonymous,
That's a good question! The game ends when the Angel can prove that she can always evade capture. She doesn't have to actually go through the motions of escaping forever :-)
"How can the Angel ever win, if his only goal in winning is to continue forever?"
It can be shown (albeit not entirely trivially) that if the devil can stop the angel from moving forever, then the devil can trap the angel inside of some huge square around the center. The devil wins when he can trap the angel. The angel wins when he can't.
"Can someone fill in the argument for me?"
I've sent you an email doing so. If anyone else wants one, just ask.
These comments have been invaluable to me as is this whole site. I thank you for your comment.
Post a Comment
<< Home