Another Concise Open Problem post by Scott Garrabrant 1271 days ago | Nate Soares and Patrick LaVictoire like this | 1 comment 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 $\lim_{n\rightarrow\infty}\prod_{i=0}^n\frac{|1-e_i-P(i)|}{|1-e_i-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(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)

NEW DISCUSSION POSTS

[Note: This comment is three
 by Ryan Carey on A brief note on factoring out certain variables | 0 likes

There should be a chat icon
 by Alex Mennen on Meta: IAFF vs LessWrong | 0 likes

Apparently "You must be
 by Jessica Taylor on Meta: IAFF vs LessWrong | 1 like

There is a replacement for
 by Alex Mennen on Meta: IAFF vs LessWrong | 1 like

Regarding the physical
 by Vanessa Kosoy on The Learning-Theoretic AI Alignment Research Agend... | 0 likes

I think that we should expect
 by Vanessa Kosoy on The Learning-Theoretic AI Alignment Research Agend... | 0 likes

I think I understand your
 by Jessica Taylor on The Learning-Theoretic AI Alignment Research Agend... | 0 likes

This seems like a hack. The
 by Jessica Taylor on The Learning-Theoretic AI Alignment Research Agend... | 0 likes

After thinking some more,
 by Vanessa Kosoy on The Learning-Theoretic AI Alignment Research Agend... | 0 likes

Yes, I think that we're
 by Vanessa Kosoy on The Learning-Theoretic AI Alignment Research Agend... | 0 likes

My intuition is that it must
 by Vanessa Kosoy on The Learning-Theoretic AI Alignment Research Agend... | 0 likes

To first approximation, a
 by Vanessa Kosoy on The Learning-Theoretic AI Alignment Research Agend... | 0 likes

Actually, I *am* including
 by Vanessa Kosoy on The Learning-Theoretic AI Alignment Research Agend... | 0 likes

Yeah, when I went back and
 by Alex Appel on Optimal and Causal Counterfactual Worlds | 0 likes

> Well, we could give up on
 by Jessica Taylor on The Learning-Theoretic AI Alignment Research Agend... | 0 likes