Consider any language $L$. Define $s(L) \in {\lbrace 0, 1 \rbrace}^\omega$ (an infinite sequence of bits) by the recursive formula
$$s(L)_n=\chi_L(s(L)_{<n})$$
Here $\chi_L$ is the characteristic function of $L$ i.e. $\chi_L(w)=1$ for $w \in L$, $\chi_L(w)=0$ for $w \notin L$
A language $U$ is called a "universal predictor" when
$$\forall L \in \mathsf{R} \, \forall n>>0:s(L)_n=\chi_U(s(L)_{<n})$$
A famous example is Solomonoff induction
It is easy to see $U \notin \mathsf{R}$ by considering $L = U^c$. The question is
Is there a universal predictor $U \in \mathsf{P/poly}$?
More specifically
Is Solomonoff induction in $\mathsf{P/poly}$?
It is not hard to see that a positive answer would imply $\exists A \in \mathsf{TALLY}:\mathsf{R} \subset \mathsf{E}^A$ ($A$ is s.t. $U$ is Cook-reducible to $A$ and we have $\mathsf{R} \subset \mathsf{E}^A$ since it is possible to apply $U$ to the sequence $\chi_L(n)$ to decide $L$ in exponential time). This implication seems surprising but I don't see why it's necessarily false
EDIT: Actually such $A$ exists:
$\lbrace w | \exists i,j \in \mathbb{N} : i \in L_j$ and $|w| = f(i,j) \rbrace$
Here $f : \mathbb{N}^2 \rightarrow \mathbb{N}$ is a bijection computable in polynomial time and $L_j$ is the $j$-th recursive language (I'm using an arbitrary enumeration of the recursive languages)
However a universal predictor in $\mathsf{P/poly}$ implies a stronger statement, namely, that there is $A \in \mathsf{TALLY}$ and some fixed polynomial $p(n)$ such that all languages in $\mathsf{TALLY} \cap \mathsf{R}$ can be computed in time $p(n)$ given an oracle for $A$
EDIT: The answer to the first question is positive. Showing this is equivalent to constructing a Turing machine with a special tape on which some fixed (input-independent) infinite string is written in the initial state s.t. this machine computes a universal predictor in polynomial time. To do this, imagine the special tape to be 2-dimensional. In row $i$ of the tape write infinite computable sequence number $i$ (i.e. computed by program $i$). The predictor then works as follows. Given an input of length $n$ it compares it to the first $n$ infinite computable sequences. The first sequence which matches the input is used for the prediction. If no sequence yields a match the predictor outputs $0$.
