God and the Devil decide to play a game. God will start by picking an infinite sequence of moves of the form "left", "right", "up", and "down". The Devil responds by creating a finite maze with an exit and by placing God somewhere inside. God then follows His pre-selected sequence to traverse the maze. Unmakable moves are ignored; for example, if the next move is "left" and there is a wall to the left of the current square, God goes on to the next move in the sequence without moving.

If God escapes the maze in finite time, He wins. Otherwise, the Devil wins.

Assuming both agents act optimally, who will win?

(assume that the maze is formed by deleting some edges from a rectangular grid, and that it has no isolated regions; i.e., it is always possible to get to the exit from any point inside the maze)

(In reply to Waaw, all those comments, just for $ 20. by Hugo)

Unfortunately, Hugo, if the devil blocks the solution in God's list, he either (1) makes his maze inescapable...no escape route, which would violate the rule, (2) he makes his maze infinitely large, which also violates the rule, or (3) there is another finite-length escape route.  Whatever that new escape route is, it HAS to be somewhere in God's list--perhaps earlier, or perhaps later in the infinite sequence.  God doesn't have to touch his list for this to be true.

Here's another way of putting it that avoids your philosophical issues with infinity:  God declares that he can create a FINITE sequence according to a certain algorithm that generates a certain immutable sequence of moves of any desired length. He presents this algorithm to the devil challenging him to build a maze that cannot be escaped from using the sequence that this algorithm generates.  The devil looks at the algorithm, and constructs a finite maze that he's sure will cause God's sequence to loop inside the maze indefinitely, no matter how far God carries it out, as long as he keeps it finite.  He presents his maze back to God, who says, "Look, all I have to do is generate moves using the algorithm for n moves (God declares what n is for that maze), and I'll escape your maze."  God can do this WITHOUT changing the algorithm and without ever creating an infinite sequence, no matter what finite maze the devil gives hiim.   All he has to do is carry it out far enough.  That's what we've proved.

Posted by Ken Haley on 2005-02-12 17:45:46