Sunday, April 15, 2007

Hypergaming

I had a short chat with one of the prospective Ph.D. students recently in which he told me about the hypergame paradox. Suppose we have a set of finite games. Finite games are games which must end in a finite number of turns. What are games? The guy said that it was just the intuitive notion of a game. I didn't get more detail so I won't give more. Hypergame is a game in which the only move available is to pick a finite game, then that game is played to completion, at which point hypergame is over. The question is: is hypergame a finite game? Suppose it is, then for each move pick to play hypergame. It never ends, so it isn't finite. Suppose it isn't. Then pick any game from the set of finite games, and that will end in a finite number of steps, and so will hypergame. Therefore it is finite. Boom. Paradox.

I was trying to figure out where the paradox comes from. At first I thought it was because hypergame was impredicative. This was probably because I've been thinking about Russell, his paradox, and such a lot lately. I couldn't really formulate how this was supposed to work though. I eventually came around to thinking that there was probably a way of reducing this to the halting problem. The idea is this. Hypergame is a Turing machine that tells you whether other Turing machines (games) halt (end in a finite number of steps). As Turing taught us, such a machine cannot exist on pain of paradox. All that is needed to get this to work is a precise way of correlating games with Turing machines. Unfortunately, I didn't get enough details for this. No idea what exactly constitutes a game, so no idea of how to line up games with Turing machines in anything more than a handwavy, metaphorical way. Alas!

9 comments:

Jason said...

is the hypergame scenario any different than the following: hyperfunc is a function taking a single non-recursive function as value. Is hyperfunc recursive?

Nick Beckstead said...

I'm the prospective who told you about the paradox. You were right about the relation of the hypergame paradox to the halting problem. See the following for more info:

Playing Games with Games: The Hypergame Paradox

William S. Zwicker

The American Mathematical Monthly, Vol. 94, No. 6. (Jun. - Jul., 1987), pp. 507-514.

Shawn said...

Hi Nick,
Thanks for the heads up. I'll check out the article in the near future.

Best of luck at Rutgers (it was Rutgers right?). I'm sure it will work out well.

Kenny said...

I'm tempted to agree with you about impredicativity being the problem - it's basically Russell's paradox.

Shawn said...

I couldn't come up with a good way of showing that impredicativity, which was a little disappointing. I also thought it was just like Russell's paradox, which fueled the impredicativity intuition. This makes me wonder, though, if there is a connetion between incomputability and impredicativity. I have no idea. This seems like the sort of thing Sol Feferman has written an insightful article (or two) about…

Ran (neko) said...

After a short thought, I came to terms with the fact that Hypergame is neither finite nor infinite.
What do I mean? It simply MIGHT be finite or MIGHT be infinite. Take for example this simple game:
1. Flip a coin. If the result is heads, wait forever. If tails, stop.

This "game" is neither finite nor infinite, just like Hypergame, only more readily seen.

Can anyone find any problem with my observation?

Shawn said...

I'm not sure what you mean. Is the "might" supposed to express an epistemic possibility? Or, do you mean that we can't prove that it isn't finite and similarly for infinite (treating "might" as "not provable not")? It doesn't seem to get around the paradox anyway. Reasoning by cases on each of the possibilities gets you the paradoxical result again.

The example game you gave is finite counting by number of turns. It is only infinite if we count by time elapsed and if time is unending. Counting by time seems like an easy assumption to drop.

Ran (neko) said...

@Shawn:
Or, do you mean that we can't prove that it isn't finite and similarly for infinite (treating "might" as "not provable not")?

I mean the two are not contradicting. Maybe our notion that everything must be EITHER finite OR infinite is wrong?

It doesn't seem to get around the paradox anyway. Reasoning by cases on each of the possibilities gets you the paradoxical result again.

I can't see how to get around the paradox, so I'm offering a different viewpoint on our most basic assumptions.

The example game you gave is finite counting by number of turns.
So instead of saying "run forever" I say "play the game 3 in a row until someone wins" which would obviously be infinite if both sides have basic computation abilities (then it always ends with a draw).

Ran (neko) said...

I think I got deeper: The paradox lies on the assumption that the sum of finite numbers is finite which is wrong. 1+1+1+1+... is not a finite number. Thus the definition of Hypergame doesn't imply that it is finite.

The amusing thing is it is still impossible to find a specific finite game to play for which Hypergame would be infinite.