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)∈S, we define the function P(n)=p if M halts on input n in time nk and outputs a probability p, and P(n)=1/2 otherwise.
Let E=e1,e2,… be an infinite bit string. We say Q∈S defeats P∈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(e1,…,en) 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∈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 liminf, and require that P∈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)
I am still curious about this question, but am much less optimistic that an answer to it would be very valuable than I was when I first asked it.