To prove this, let us assume, on the contrary, that a Nash equilibrium exists
and in it Player 1's strategy is a mixture of the algorithms
(*A*_{0}, *A*_{1},...). Each of these
*A*_{i} algorithms has a positive mixture probability,
*P*_{i}, and these probabilities must sum up to 1:

Per the definition of "lim", this means that for any ε there is an
*n* such that

So, for example, let us choose ε to be 1/3, then

This means that with probability of at least 2/3, the chosen strategy is one of
the finite range *A*_{0},..., *A*_{n}.

We can now define a strategy *B* for Player 0 as follows:

Let {x_r} be Player 0's previous bits. Let {y_r} be Player 1's previous bits. Let i = |{r | x_r != y_r }| # This is the number of rounds where Player 0 "lost". If i>n: Return 0 Else: Return the result of A_i on the input ({y_r},{x_r}). # i.e., return what Player 1 would have returned if its strategy was A_i.

If Player 0 was to follow this strategy and Player 1's algorithm, as determined
probabilistically from the mixed strategy, was one of
*A*_{0},..., *A*_{n}, the total number of
rounds that Player 0 would have lost in would have been bounded by *n*,
so the final score would have been 0 -- a flat out win for Player 0. This
happens in probability of at least 2/3. In the remaining 1/3, at worst
Player 1 wins every round. This would bring the total final score to at most
1/3. In other words, regardless of what Player 1's strategy is, Player 0 can
always ensure an expected score of 1/3 or lower. Any Nash equilibrium must
therefore have this as its score.

However, we can just as easily design the corresponding strategy for Player 1, defending against a known strategy mix from Player 0. This would be identical to the program described above, with only a change in the final line. Now it would be:

Return the complement of the result of A_i on the input ({y_r},{x_r}).

In this way, by exactly the same argument as before, Player 1 can ensure an expected final score in excess of 2/3, so any Nash equilibrium must, similarly, have at least 2/3 as its score. We reach a contradiction.

Let {x_r} be Player 0's previous bits. Let {y_r} be Player 1's previous bits. Let i = |{r | x_r != y_r }| # This is the number of rounds where Player 0 "lost". Return the result of A_i on the input ({y_r},{x_r}), where {A_i} is an enumeration over all possible Turing machines.

It is not difficult to enumerate over all Turing machines, if one is willing to
enumerate also over non-halting machines (which, in this part of the riddle,
we are willing to do).
Player 1's algorithm, regardless of what mixed strategy it was chosen
from, is ultimately equivalent to a Turing machine. So, it is some
*A*_{i} in our enumeration over Turing machines. That
being the case, the total number of rounds Player 0 will have lost during the
game can never exceed the constant *i*, so the final score will be 0.

As there is nothing Player 1 can do about this, and as a score of 0 is the best possible outcome for Player 0, the strategy forms a Nash equilibrium together with any strategy by Player 1.

We remark that in this part Player 1 cannot copy the same idea, inverting the
output of *A*_{i}, as happened in Part 1, because
*A*_{i} may never halt, something that Player 1 cannot, in
general, check.