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

limn→∞n∏i=0|1−ei−P(i)||1−ei−Q(i)|=0.

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)

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

limn→∞n∏i=0|1−ei−P(i)||1−ei−Q(i)|=0.

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)