So after watching the last Stanley cup game, a problem popped up in my head for which I have no solution. Say we have a game, like a hockey game, that has the possibility of going on forever. Of course, it does not usually go on forever, nor have we ever seen it go on forever. But we'd like to! We also would like to see every single possible outcome that could happen in the game. Naturally, there are an infinite number of possible outcomes, as this is a mathematically pure game uninhibited by the inelegant rules of our physical realm. However, this does not stop us! We decide to create an algorithm to enumerate all possible outcomes. It's very simple, it proceeds as thus:

While True:
    Play a new game

Now, as we have already stated, one of the possible outcomes of playing a new game is having a game that runs on forever. According to the infinite monkey theorem, this is bound to happen at some point. But when it does, we will be unable to continue this algorithm, as it is impossible to say whether or not the game goes on forever before it, well, erm, goes on forever (halting problem).

So here's where I'm stuck. Does this mean it's impossible to enumerate all possible outcomes of playing this game? Is finding all possible outcomes undecidable (even though there are an infinite number of outcomes so finding all solutions is inherently impossible)?

Unfortunately, I do not have the education (yet!) to deduce the solution with proper vocabulary. I'm sure this problem has existed for a long while in some other form (I'm thinking halting problem, or somehow closely related), so this shouldn't be very mysterious. Thanks!

  • $\begingroup$ There's no need to wait until a game is over to start a new one, right? This is basically how you enumerate the "halting set": at each time, start a new Turing machine on its input and look to see which of the previously-started machines have halted. $\endgroup$ Jun 20 '13 at 5:21
  • $\begingroup$ It's not so clear that you can use the infinite monkey theorem here because there's too many (infinitely many) possible lengths of each game. It seems like you will have to pick a probability distribution on the game lengths. Also, probability 1 doesn't strictly mean "bound to happen". $\endgroup$
    – Cocopuffs
    Jun 20 '13 at 5:40

The way to do it would be to interleave plays in the game. This is akin to how we can simulate all computations, even the ones that don't halt: run step one of the first computation, then step one of the second, then step two of the first, then step two of the second, then step one of the third...


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.