Personal Blog

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 be the set of all paris where is a Turing machines which and is a natural number.

For , we define the function if halts on input in time and outputs a probability , and otherwise.

Let be an infinite bit string. We say defeats on if

If there is no in which defeats on , we say that is undefeated on .

Let be an algorithm which takes as input a finite bit string, and whose output encodes an element of .

Does there exist an algorithm such that for all , if there exists a which is undefeated on , then for all sufficienty large , is undefeated on ?

Note that can run as long as it wants. I would also be very interested in a positive result that requires that is undefeated by every function computable in exponential time. ( still runs in polynomial time.)

Also, note that if I replace the with , and require that is undefeated by every function computable in exponential time, then such an 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)

New Comment
1 comment, sorted by Click to highlight new comments since: Today at 6:49 AM

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.