A while ago I wrote a post on hypergame, a paradox that was pointed out to me by a visiting prospective student. He was nice enough to post the reference to an article by the inventor of the paradox: Playing Games with Games:
The Hypergame Paradox
William S. Zwicker
The American Mathematical Monthly, Vol. 94, No. 6. (Jun. – Jul., 1987), pp. 507-514
My intuition was that the problem came down to the halting problem but I wasn’t sure how to get a correspondence between games and Turing machines. It turns out that Zwicker does basically that. He suggests for any game, you associate a program that allows the players to input their moves and plays out exactly as the game does. This isn’t much more formal than the idea in my earlier post. It does lead quickly to the source of the paradox: it assumes the existence of a Turing machine that can solve the halting problem. He also gave another way of looking at it. Identify each game with its game tree of possible moves. Finite games are then trees that well-founded. The question becomes: is the tree consisting of the trees of all well-founded trees itself well-founded? This, apparently, connects up with existing research in set theory. There is also a little discussion of the nature of mathematical paradox in the article, including a quote from an article Quine wrote on paradoxes for Scientific American. I had never seen that article before, so that was kind of cool. Zwicker’s article is a fun read as well as insightful.