\section{Proofs for Sections~\ref{sec:average} and~\ref{sec:transformers}}\label{app:average}

\proplprgfalse*

\begin{proof}[Proof of \cref{prop:lprgfalse}]
\begin{steps}
\step{1}{1} \Let $m=\lceil\alpha N\rceil\ge2N$, and \Let the algorithm $A$, on input $(\tau,z)$, form the context
$S=((\tau_j,z_j))_{j\le m}$ of $\RL_P$, compute $|\VS(S)|$, and output $1$ if and only if $|\VS(S)|>0$. Then $A$ is
deterministic and runs in time $\poly(N)\cdot2^{O(N\log\log N/\sqrt{\log N})}$.
\pf $\RL_P$ is $k$-local, so \cref{fact:vs} takes time $\poly(N,m)\cdot2^k\cdot2^{C_1k^2g(N)}$, with $k$ and $\alpha$
constant.
\step{1}{2} On outputs of the generator, $A$ outputs $1$ with probability $1$.
\pf The task $w$ lies in $\VS(S)$.
\step{1}{3} On uniform $z$, $A$ outputs $1$ with probability at most $2^{-N}$.
\pf For fixed $\tau$, $\VS(S)\ne\emptyset$ means that $z$ is one of the at most $2^N$ strings $G_{P,m}(\tau;w')$,
and $z$ is uniform among $2^m\ge2^{2N}$ strings.
\qedstep{1}{4}
\pf The advantage of $A$ is at least $1-2^{-N}>1/3$ at every $N$. For $c<1/2$, the exponent
$N\log\log N/\sqrt{\log N}$ is $o(N/(\log N)^c)$, so the time of $A$ is at most $2^{N/(\log N)^c}$ for large $N$.
So $G_{P,\lceil\alpha N\rceil}$ is not $2^{N/(\log N)^c}$-pseudorandom, for any $k$, $P$ and $\alpha\ge2$, and no
choice of $\alpha_0$ in $\lenLPRG{c}$ works.
\end{steps}
\end{proof}

\thmregimes*

\begin{proof}[Proof of \cref{thm:regimes}]
\begin{steps}
\step{1}{1} Part~\ref{it:rbayes} holds.
\pf \Cref{thm:risk}\ref{it:bound} without noise, and \cref{thm:bayesalg}\ref{it:noiseless} with $\kappa=k$
constant, where $\poly(N,m)\cdot2^k\cdot T_k(N)=\poly(m)\cdot2^{O(N\log\log N/\sqrt{\log N})}$.
\step{1}{2} Part~\ref{it:rlin} holds.
\pf \Cref{thm:regression}\ref{it:alin} with $\kappa=k$, where $D_k(N)\le(eN/k)^k=O(N^k)$, so
$\mVC(D_k(N)+1,\eps,\delta)=O((N^k\log(1/\eps)+\log(1/\delta))/\eps)$ and the time is $\poly(N,m)$.
\step{1}{3} Part~\ref{it:rlower} holds.
\begin{steps}
\step{2}{1} \Let $A'$, on input $(\tau_1,\dots,\tau_{m+1},z_1,\dots,z_{m+1})$, run $A$ on the context
$((\tau_j,z_j))_{j\le m}$ and the query $\tau_{m+1}$, and output $1$ if and only if the prediction equals
$z_{m+1}$. Then $A'$ runs in time $T_A+c_*(m+1)k\log N$ for an absolute constant $c_*$, and if $m(N)$ is computable
in time polynomial in $N$, $A'$ is one algorithm for all $N$.
\pf Besides running $A$, $A'$ copies its input, which has $O((m+1)k\log N)$ bits, and compares two bits. The
number $m$ is read off the length of the input.
\step{2}{2} On outputs of the generator, $A'$ outputs $1$ with probability $1-R_m(A)$.
\pf For uniform $w$ and independent uniform tuples, $(\tau,G_{P,m+1}(\tau;w))$ is a noiseless episode of length
$m$ of the task family $(\RL_P,\cD_k)$, with target $z_{m+1}$.
\step{2}{3} On uniform $z$, $A'$ outputs $1$ with probability $1/2$.
\pf $z_{m+1}$ is uniform and independent of the context, of the query and of the random bits of $A$.
\qedstep{2}{4}
\pf The advantage of $A'$ is $|1-R_m(A)-1/2|=|1/2-R_m(A)|$ by \sref{2}{2} and \sref{2}{3}.
\end{steps}
\qedstep{1}{4}
\end{steps}
\end{proof}

\corregimes*

\begin{proof}[Proof of \cref{cor:regimes}]
\begin{steps}
\step{1}{1} Part~\ref{it:cpoly} holds.
\begin{steps}
\step{2}{1} \Let $A''$, on an input with $\lceil N^s\rceil$ outputs, compute $m(N)$ and run the algorithm $A'$ of
\cref{thm:regimes}\ref{it:rlower} on the first $m(N)+1$ outputs and their tuples. Then $A''$ is one algorithm,
it runs in time polynomial in $N$, and its advantage against $G_{P,\lceil N^s\rceil}$ is $|1/2-R_{m(N)}(A)|$.
\pf $A$ runs in time polynomial in its input, whose length is polynomial in $N$ because
$m(N)\le N^s$, and $m(N)$ is computable in polynomial time. The first $m(N)+1$ outputs of
$G_{P,\lceil N^s\rceil}$ with their tuples are distributed as $G_{P,m(N)+1}$, and those of a uniform string are
uniform, so the advantage is that of $A'$.
\step{2}{2} $R_{m(N)}(A)\ge1/6$ for all sufficiently large $N$.
\pf By $\LPRG_s$ the advantage of $A''$ is at most $1/3$ for all large $N$, so $|1/2-R_{m(N)}(A)|\le1/3$.
\qedstep{2}{3}
\pf At $m=\lceil N^s\rceil-1$, \cref{thm:regimes}\ref{it:rbayes} gives $R^*_m\le N/\lceil N^s\rceil\le N^{1-s}$, and
\cref{thm:regimes}\ref{it:rlin} with $\delta=\eps/2$ and $\eps/2$ in place of $\eps$ gives the claim for $\Alin$.
\end{steps}
\step{1}{2} Part~\ref{it:clen} holds.
\pf Here $m(N)+1=\lceil\alpha N\rceil$ is computable in polynomial time. The algorithm $A'$ of
\cref{thm:regimes}\ref{it:rlower} for $A$ runs in time $2^{N/(\log N)^c-1}+c_*\lceil\alpha N\rceil k\log N\le2^{N/(\log
N)^c}$ for large $N$, so by $\lenLPRG{c}$ with this $\alpha\ge\alpha_0$ its advantage
$|1/2-R_{m(N)}(A)|$ is at most $1/3$ for all large $N$, and $R_{m(N)}(A)\ge1/6$. The Bayes risk is at most
$N/(m(N)+1)=N/\lceil\alpha N\rceil\le1/\alpha\le1/7$, and the time of the Bayes predictor is that of
\cref{thm:regimes}\ref{it:rbayes} with $m=O(N)$.
\qedstep{1}{3}
\end{steps}
\end{proof}

\cortransformers*

\begin{proof}[Proof of \cref{cor:transformers}]
\begin{steps}
\step{1}{1} \Let $\mathcal S$ be the algorithm that, given an input of dimension $N$, computes the parameters of
$M_N$ and generates its chain of thought and answer. On a prompt of length $\ell$ it runs in time at most
$N^{O(1)}+(p+\ell+L(N))^{c_M+1}$, and on the inputs of each part $\ell\le N^{O(1)}$.
\pf The family is uniform, each of the at most $L(N)+1$ generated tokens takes time at most
$(p+\ell+L(N))^{c_M}$, and in every part the contexts have polynomially many examples: at most $N^{c_\gamma}$ in
\ref{it:tseth}, at most $36N^2$ in~\ref{it:tlen}, and $m(N)\le N^s$ in~\ref{it:tprg} and~\ref{it:tlenprg}.
\step{1}{2} Part~\ref{it:tseth} holds.
\pf Suppose that $L(N)\le2^{(1-\gamma)N/(c_M+1)}-p(N)-\ell_{\max}(N)$ for all large $N$, where $\ell_{\max}(N)\le
N^{O(1)}$ is the largest prompt length. Then $\mathcal S$ computes $\Bayes(S,x)$ on all the contexts of
\cref{thm:hardness}\ref{it:seth} in time $N^{O(1)}+2^{(1-\gamma)N}=O(2^{(1-\gamma)N})$, which that theorem excludes.
\step{1}{3} Part~\ref{it:tlen} holds.
\pf Suppose that $L(N)<2^{N/(\log N)^{C+\theta}}$ for all large $N$. Then the time of $\mathcal S$ is at most
$N^{O(1)}+(N^{O(1)}+2^{N/(\log N)^{C+\theta}})^{c_M+1}\le2^{(c_M+2)N/(\log N)^{C+\theta}}\le2^{N/(\log N)^{C+\theta/2}}$
for large $N$, which \cref{thm:hardness}\ref{it:len} with $\theta/2$ in place of $\theta$ excludes.
\step{1}{4} Part~\ref{it:tprg} holds.
\pf With $L(N)\le N^{O(1)}$, $\mathcal S$ is a polynomial-time in-context learner; apply
\cref{cor:regimes}\ref{it:cpoly}.
\qedstep{1}{5}
\pf For part~\ref{it:tlenprg}, if $L(N)\le2^{N/((c_M+2)(\log N)^c)}$ for all large $N$, the time of $\mathcal S$ on
contexts of length $m(N)=O(N)$ is at most $N^{O(1)}+(N^{O(1)}+2^{N/((c_M+2)(\log N)^c)})^{c_M+1}$, which is at most
$2^{N/(\log N)^c-1}$ for large $N$. Apply \cref{cor:regimes}\ref{it:clen}.
\end{steps}
\end{proof}