Given the success of the last open problem I posted, (Janos Kramer disproved my conjecture) I decided to post another one. Again, I will cut off the philosophy, and just give the math. The reason I want this result is to solve the problem described here.
Let \(S\) be the set of all paris \((M,k)\) where \(M\) is a Turing machines which and \(k\) is a natural number.
For \(P=(M,k)\in S\), we define the function \(P(n)=p\) if \(M\) halts on input \(n\) in time \(n^k\) and outputs a probability \(p\), and \(P(n)=1/2\) otherwise.
Let \(E=e_1,e_2,\ldots\) be an infinite bit string. We say \(Q\in S\) defeats \(P\in S\) on \(E\) if
If there is no \(Q\) in \(S\) which defeats \(P\) on \(E\), we say that \(P\) is undefeated on \(E\).
Let \(A\) be an algorithm which takes as input a finite bit string, and whose output encodes an element of \(S\).
Does there exist an algorithm \(A\) such that for all \(E\), if there exists a \(P\) which is undefeated on \(E\), then for all sufficienty large \(n\), \(A(e_1,\ldots,e_n)\) is undefeated on \(E\)?
Note that \(A\) can run as long as it wants. I would also be very interested in a positive result that requires that \(P\in S\) is undefeated by every function computable in exponential time. (\(P\) still runs in polynomial time.)
Also, note that if I replace the \(\lim\) with \(\lim \inf\), and require that \(P\in S\) is undefeated by every function computable in exponential time, then such an \(A\) does in fact exist. (The algorithm that does this has not been posted on the forum yet, sorry. If anyone wants to work on this problem, and is curious, I can explain it to them)