Zero-Sum Games and Halting Problem

Question

Wikipedia states on the page of the halting problem, "For any program f that might determine if programs halt, a "pathological" program g called with an input can pass its own source and its input to f and then specifically do the opposite of what f predicts g will do."

Suppose we have 2 neural networks, approximating f and g (allowing infinite size and depth limits). Is it wrong to assume that these two NNs can participate in a zero-sum game against each other, and that the Nash equilibrium (if it exists) of these 2 NNs contains the solution to the halting problem?

Answer 1

It is not quite clear to me what you have in mind with infinite size + depth limits for your neural net, but once you have sorted that out you should end up with the following game:

Player I plays a program p, and Player II plays a program q.

Player 1 wins iff p halts on input q, and answer Yes if q halts on input q, and No otherwise. Player 2 wins iff Player 1 doesnt.

This game has no Nash equilibrium. Player I always has a winning best response amongst the programs "just output Yes" and "just output No". The diagonalization construction from the proof that the Halting problem is undecidable tells us how Player II could compute a winning best response if she knew Player I's choice p.

Answer 2

Turing proved that the halting problem is undecidable.

No algorithm that you can come up with will solve the halting problem.