Today I've heard about fascinating metagame paradox. I tried to come up with an explanation via Turing Machines formalization (below). Do you know what is the solution to the paradox? (the post content: definition - proposed solution - conclusion)
Something is a game iff:
G1. Two players G2. Players alternate G3. The game finally ends.
The metagame is:
M1. First player picks a game M2. Second player starts the game M3. The winner is the winner of the game at step 2.
Example of a metagame:
1) I pick tic-tac-toe 2) OK, I put X here .. .. so they play .. 3) .. and let player 2 wins in the tic-tac-toe => player 2 wins the metagame.
Paradox: Is metagame a game?
If metagame is a game, then at point (M1) both players can always pick a metagame, so the metagame will never end => (G3) is violated => metagame is not a game => contradiction.
(also contradiction for case "metagame is not a game" -- metagame will satisfy the definition of a game)
What is the solution to the paradox?
UPDATE: You may want to skip this explanation and go directly to D.W. answer.
I came up with the following explanation:
Lets formalize the problem using Turing Machines notations. Let a game be a finite binary string that describes "somehow" game rules. Let a game simulator be a non-deterministic TM that reads a description from the input (without any sanity checks, so the TM doesn't know if the game finally ends), and then makes non-deterministic moves for the first and second player. Here we assume (A1) that the game-simulator can decide valid next moves.
Now have a look at the description of a meta-game:
M1. First player picks a game
This sentence means that we can "pick a game", i.e. in the definition we assume (A2) that whether an arbitrarily binary string is a game (satisfies G1,G2,G3) is decidable. (see also note (n1) )
M2 and M3 look decidable.
So, my suggestion is that metagame is not "defined properly", since its definition assumes the existence of a decider "if a given binary string is a game". And then we derive a contradiction, so this assumption is wrong.
Does it make sense? Is this related with other explanations of the paradox? (intuitive answers would be great!)
- Assuming "whether an arbitrarily binary string is a game" may be too much. But we need some computable procedure "pick a game" and one that came into mind is "generate random string, check if it is a game".
- I don't know what is a formal word for "not defined properly"
- Assumption A1 may also be undecidable, but I believe it should not change the argument..