<EMAIL_ADDRESS>
# Learning Universal Predictors

Jordi Grau-Moya  Equal contributions.  Google DeepMind, London, United Kingdom
Tim Genewein  Equal contributions.  Google DeepMind, London, United Kingdom
Marcus Hutter  Equal contributions.  Google DeepMind, London, United Kingdom
Laurent Orseau  Equal contributions.  Google DeepMind, London, United Kingdom
Grégoire Déletang  Elliot Catt  Anian Ruoss  Li Kevin Wenliang  Christopher
Mattern  Matthew Aitchison  Joel Veness

###### Abstract

Meta-learning has emerged as a powerful approach to train neural networks to
learn new tasks quickly from limited data. Broad exposure to different tasks
leads to versatile representations enabling general problem solving. But, what
are the limits of meta-learning? In this work, we explore the potential of
amortizing the most powerful universal predictor, namely Solomonoff Induction
(SI), into neural networks via leveraging meta-learning to its limits. We use
Universal Turing Machines (UTMs) to generate training data used to expose
networks to a broad range of patterns. We provide theoretical analysis of the
UTM data generation processes and meta-training protocols. We conduct
comprehensive experiments with neural architectures (e.g. LSTMs, Transformers)
and algorithmic data generators of varying complexity and universality. Our
results suggest that UTM data is a valuable resource for meta-learning, and
that it can be used to train neural networks capable of learning universal
prediction strategies.

###### keywords:

Kolmogorov-complexity, universal prediction, in-context learning

Figure 1: Summary of our meta-learning methodology.

Meta-learning has emerged as a powerful approach to enable AI systems to learn
new tasks quickly from limited data (Hospedales et al., 2021). By training a
model on a diverse set of tasks, meta-learning encourages the discovery of
representations and learning strategies that generalize to new, unseen tasks.
Intriguingly, recent research has shown that, when exposed to specific data
regimes, meta-learning allows neural networks to perform Bayesian inference
(Ortega et al., 2019; Mikulik et al., 2020; Genewein et al., 2023), which is
critical for principled prediction under uncertainty. A key challenge in meta-
learning is to design task distributions that are sufficiently broad, exposing
the model to a rich variety of structures and patterns. Such broad exposure
could lead to “universal” representations, enabling the system to tackle a
wide range of problems and bringing us closer to the goal of artificial
general intelligence (AGI).

Solomonoff Induction 111 SI arguably solved the century-old induction problem
(Rathmanner and Hutter, 2011), is the basis of the Hutter prize (Hutter,
2006/2020) and has been praised by the father of AI, Marvin Minsky: “the most
important discovery since Gödel”. (SI) offers a compelling theoretical
foundation for constructing such an ideal universal prediction system
(Solomonoff, 1964a, b) 222For an introduction see (Hutter et al., 2007;
Hutter, 2017) and see (Hutter, 2007) for technical details. . At its core, SI
elegantly integrates three fundamental principles (see Figure 1).
_Consideration of all computable hypotheses:_ Unlike traditional approaches,
SI explores the entire space of computable hypotheses (i.e. generated by a
computer program) as potential explanations for observed data. _Occam’s
Razor:_ SI assigns higher prior probabilities to simpler hypotheses with
shorter descriptions. _Bayesian Updating_ : With new data, SI employs Bayes’
rule to refine its belief about each hypothesis. The theoretical strength of
SI lies in its ability to rapidly converge on the true data-generating
process, if computable (Li and Vitanyi, 1992; Hutter, 2004; Sunehag and
Hutter, 2013; Li et al., 2019). Yet, a significant barrier is its practical
incomputability. The exhaustive exploration of algorithmic hypotheses demands
immense computational resources. To address this, approximations of SI were
developed e.g. the Speed Prior (Schmidhuber, 2002; Filan et al., 2016) and the
Context Tree Weighting algorithm (Willems et al., 1995; Willems, 1998; Veness
et al., 2012).

To understand the power of SI, imagine a program that generates an infinite
stream of data $x$, e.g., a fluid dynamics simulation or an AI movie
generator. Let’s say the length of the shortest possible version of this
program (i.e. its Kolmogorov complexity (Li et al., 2019)) is $N$ bits long,
where all unnecessary elements have been removed and we have used compression
to further reduce the size. Now, if we feed the data stream $x$ to SI and let
it predict each bit, something remarkable happens: After making fewer than $N$
prediction errors, SI will predict future data perfectly! This occurs because
SI effectively learns the underlying rules of the data-generating program.
With each incorrect prediction, it eliminates a range of possible
explanations, allowing it to quickly find the correct program behind the data.

In this paper, we explore the potential of amortizing Solomonoff Induction
into neural networks via meta-learning (see Figure 1). A key challenge is
finding neural architectures and training data distributions that guide
networks towards learning SI in the limit. While neural networks are
theoretically capable of universal computation (Chen et al., 2017; Stogin et
al., 2020; Mali et al., 2023), practical training methods (e.g., stochastic
gradient descent) can limit this ability (Deletang et al., 2022). Here we
simply use off-the-shelf architectures like Transformers and LSTMs, while
focusing on designing a suitable data training protocol. To address this, we
generate data from Universal Turing Machines (UTMs), which are fully general
computers. Training on this “universal data” exposes the network to a broad
space of computable patterns that guide the network towards learning universal
inductive strategies.

Our key contributions are: _1) UTM data:_ We use, for the first time, UTM data
to meta-train neural networks. _2) Theoretical Analysis:_ We provide a
theoretical analysis of the UTM data generation process and training protocol
that converges to SI in the limit. _3) Extensive Experiments:_ We conduct
comprehensive experiments with a variety of neural architectures (e.g. LSTMs,
Transformers) and algorithmic data generators of varying complexity and
universality. We open-sourced the generators at https://github.com/google-
deepmind/neural_networks_solomonoff_induction.

Our results show that increasing model size leads to improved performance,
demonstrating that model scaling helps learning increasingly universal
prediction strategies. We find that: Large Transformers trained on UTM data
successfully transfer their learning to other tasks suggesting they acquired
reusable universal patterns; On variable-order Markov sources, large LSTMs and
Transformers achieve optimal performance, highlighting their ability to model
Bayesian mixtures over programs necessary for SI.

##  1 Background

Notation. An alphabet $\mathcal{X}$ is a finite, non-empty set of symbols. A
string $x_{1}x_{2}\ldots x_{n}\in\mathcal{X}^{n}$ of length $n$ is denoted by
$x_{1:n}$. The prefix $x_{1:j}$ of $x_{1:n}$, $j\leq n$, is denoted by
$x_{\leq j}$ or $x_{<j+1}$. The empty string is denoted by $\epsilon$. Our
notation generalizes to out-of-bounds indices i.e. given a string $x_{1:n}$
and an integer $m>n$, we define $x_{1:m}:=x_{1:n}$ and $x_{n:m}:=\epsilon$.
The concatenation of two strings $s$ and $r$ is denoted by $sr$. The
expression $[\\![A]\\!]$ is $1$ if $A$ is true and $0$ otherwise.

Semimeasures. A semimeasure is a probability measure $P$ over infinite and
finite sequences $\mathcal{X}^{\infty}\cup\mathcal{X}^{*}$ for some finite
alphabet $\mathcal{X}$ assumed to be $\\{0,1\\}$ (most statements hold for
arbitrary finite $\mathcal{X}$). Let $\mu(x)$ be the probability that an
(in)finite sequence _starts_ with $x$. While proper distributions satisfy
$\sum_{a\in\mathcal{X}}\mu(xa)=\mu(x)$, semimeasures exhibit _probability
gaps_ and satisfy $\sum_{a\in\mathcal{X}}\mu(xa)\leq\mu(x)$.

Turing Machines. A Turing Machine (TM) takes a string of symbols $z$ as an
input, and outputs a string of symbols $x$ (after reading $z$ and halting),
i.e. $T(z)=x$. For convenience we define the output string at computation step
$s$ as $T^{s}(z)=x$ which may be the empty string $\epsilon$. We adopt similar
notation for Universal Turing Machines $U$. Monotone TMs (see Definition 1
below) are special TMs that can incrementally build the output string while
incrementally reading the input program, which is a convenient practical
property we exploit in our experiments.

######  Definition 1 (Monotonicity).

A universal machine $U$ is monotone if for all $p,q,x,y$ with $U(p)=y$ and
$U(q)=x$ we have that $\ell(x)\geq\ell(y)$ and $p\sqsubseteq q$ imply
$y\sqsubseteq x$, where $p\sqsubseteq q$ means that $p$ is a prefix string of
$q$. See Appendix C for a more thorough description.

Solomonoff Induction (SI). The optimal prediction over the next symbol
$x_{n+1}$ given an observed sequence $x_{1:n}$ is
$\mu(x_{n+1}|x_{1:n})=\mu(x_{1:n+1})/\mu(x_{1:n})$, assuming that $\mu$ is the
true (but unknown) computable probability distribution over sequences. In
contrast, SI predicts the next symbol $x_{n+1}$ using a single universal
semimeasure $M$ widely known as the Solomonoff Universal Prior (see definition
below).

######  Definition 2 ((Monotone) Solomonoff Prior).

Let $U$ be a universal monotone machine, then the Solomonoff prior is defined
as $M(x)\leavevmode\nobreak\ :=\leavevmode\nobreak\
\sum_{p:U(p)=x*}2^{-\ell(p)}$ with the sum is over all $p\in\\{0,1\\}^{*}$,
where the output $x*$ is any string that starts with $x$ _and_ the whole
program $p$ has been read by $U$.

We can use $M$ to construct the posterior predictive distribution
$M(x_{n+1}|x_{1:n})=\frac{M(x_{1:n}x_{n+1})}{M(x_{1:n})}$ (see Figure 1). This
is equivalent to performing Bayesian inference on program space
$M(x_{n+1}|x_{1:n})=\sum_{p}P(p|x_{1:n})[\\![U(p)=x_{1:n}x_{n+1}*]\\!]$ (for
prefix-free programs, and any continuation $*$ of the sequence), where
$P(p|x_{1:n})$ is the Bayesian posterior over programs given the data using
the prior $P(p)=2^{-\ell(p)}$ and the zero-one likelihood
$P(x|p)=[\\![U(p)=x*]\\!]$.

Solomonoff (1964a) showed that $M$ converges fast (to the true $\mu$) if the
data is generated by _any_ computable probability distribution $\mu$:
$\sum_{t=1}^{\infty}\sum_{x_{<t}}\mu(x_{<t})\sum_{x\in\mathcal{X}}(M(x|x_{<t})-\mu(x|x_{<t}))^{2}\leq
K(\mu)\ln 2<\infty$, where $K(\mu):=\min_{p}\\{\ell(p):U(p)=\mu\\}$ is the
Kolmogorov complexity (Li et al., 2019) of the generator $\mu$ (represented as
a bitstring). This can be seen when noticing that on the left-hand-side of the
inequality we have an infinite sum and on the right we have a constant. The
Solomonoff prior is essentially the best universal predictor given a choice of
reference UTM.

There exists a normalized version of the Solomonoff prior (among others (Wood
et al., 2013)) that is not a semimeasure but a proper measure i.e., properly
normalized (see Definition 3 below). It has nicer properties when $x$ contains
incomputable sub-sequences (Lattimore et al., 2011) and maintains the
convergence properties of the standard Solomonoff prior. This version of SI is
of interest to us because it suited to be learned by neural models (that are
also properly normalized) and exhibits more efficient sampling than
semimeasures (due to no probability gap).

######  Definition 3 (Normalized Solomonoff Prior).

For $a\in\mathcal{X}$, Solomonoff normalization is defined as
$M^{norm}(\epsilon):=1,\leavevmode\nobreak\ \leavevmode\nobreak\
\leavevmode\nobreak\ M^{norm}(a|x)\leavevmode\nobreak\ :=\leavevmode\nobreak\
\frac{M(xa)}{\sum_{a\in\mathcal{X}}M(xa)}\leavevmode\nobreak\
=\leavevmode\nobreak\ \frac{M^{norm}(xa)}{M^{norm}(x)}$.

Algorithmic Data Generating Sources and the Chomsky Hierarchy. An algorithmic
data generating source $\mu$ is simply a computable data source by, for
example, a TM $T$ fed with random inputs. There is a natural hierarchy over
machines based on their memory structure known as the Chomsky hierarchy (CH)
(Chomsky, 1956), which classifies sequence prediction problems—and associated
automata models that solve them—by increasing complexity. There are four
levels in the CH, namely, regular, context-free, context-sensitive, and
recursively enumerable. Solving problems on each level requires different
memory structures such as finite states, stack, finite tape and infinite tape,
respectively. Note that any reasonable approximation to SI would need to sit
at the top of the hierarchy.

Meta-Learning. A parametric model $\pi_{\theta}$ can be meta-trained by
repeating the following steps (see Figure 1): 1) sample a task $\tau$
(programs in our case) from the task distribution $p(\tau)$, 2) sample an
output sequence $x_{1:n}$ from $\tau$, 3) train the model $\pi_{\theta}$ with
the log-loss $-\sum_{t=1}^{n}\log\pi_{\theta}(x_{t}|x_{<t})$. Ortega et al.
(2019) showed that the fully trained $\pi_{\theta}$ behaves as a Bayes-optimal
predictor, i.e.
$\pi_{\theta}(x_{t}|x_{<t})\approx\sum_{\tau}p(\tau|x_{<t})p(x_{t}|x_{<t},\tau)$
where $p(x_{t}|x_{<t},\tau)$ is the predictive distribution, and
$p(\tau|x_{<t})$ the posterior (Ortega et al., 2019). More formally, if $\mu$
is a proper measure and $D=(x^{1},...,x^{J})$ are sequences cut to length $n$
sampled from $\mu$ with empirical distribution
$\hat{\mu}(x)=\frac{1}{J}\sum_{y\in D}[\\![y=x]\\!]$, then the log-loss
$\text{Loss}(\theta):=-\frac{1}{J}\sum_{x\in
D}\sum_{t=1}^{\ell(x)}\log\pi_{\theta}(x_{t}|x_{<t})=-\frac{1}{J}\sum_{x\in
D}\log\pi_{\theta}(x)=-\sum_{x\in\mathcal{X}^{n}}\hat{\mu}(x)\log
p_{\theta}(x)$ is minimized for $\pi_{\theta}(x)=\hat{\mu}(x)$ provided
$\pi_{\theta}$ can represent $\hat{\mu}$.

##  2 Meta-Learning as an Approximation to Solomonoff Induction

Next we aim to provide answers to the following questions. First, _how do we
generate meta-training data that allows to approximate SI?_ Second, given that
most architectures are trained with a limited sequence-length, _how does this
affect the meta-training protocol of neural models?_ Third, _can we use
different program distributions (making interesting programs more likely)
without losing universality?_

###  2.1 The right dataset: Estimating Solomonoff from Solomonoff Samples

Our aim here is to define a data generation process such that we obtain an
approximation to $M$ (see Figure 1) when training our model $\pi_{\theta}$ on
it (assuming for now universality and essentially infinite capacity). We
consider the incomputable and computable cases. All proofs can be found in the
Appendix A.

Solomonoff Data Generator (incomputable).  Putting uniform random bits $p$ on
the (read-only) input tape of a monotone UTM $U$ generates a certain
distribution $M$ of (in)finite strings $x$ on the output tape. This is exactly
Solomonoff’s prior $M$ and a semimeasure (see Section 1). Sampling from $M$ is
trivial; we just described how and coincides exactly with the standard meta-
learning setup where programs correspond to tasks. $M$ is equivalent to the
more formal Definition 2. The following proposition shows consistency.

######  Proposition 4.

Let $D:=(x^{1},...,x^{J})$ be $J$ (in)finite sequences sampled from a
semimeasure $\mu$ (e.g. $M$). We can estimate $\mu$ as follows:
$\hat{\mu}_{D}(x)\leavevmode\nobreak\ :=\leavevmode\nobreak\
\frac{1}{|D|}\sum_{y\in D}[\\![\ell(y)\geq\ell(x)\leavevmode\nobreak\
\wedge\leavevmode\nobreak\ y_{1:\ell(x)}=x]\\!]\leavevmode\nobreak\
\stackrel{{\scriptstyle w.p.1}}{{\longrightarrow}}\mu(x)\leavevmode\nobreak\
\leavevmode\nobreak\ \text{for}\leavevmode\nobreak\ \leavevmode\nobreak\
|D|\to\infty$.

Unfortunately there are three infinities which prevent us from using $M$
above. There are infinitely many programs, programs may loop forever, and
output strings can have infinite length. Therefore, we define the following
computable version of the Solomonoff prior.

######  Definition 5 (Computable Solomonoff Prior).

Let programs be of length $\leq L$ and stop $U$ after $s$ steps (denoted
$U^{s}$), or if the output reaches length $n$. Then,

$\displaystyle M_{s,L,n}(x)\leavevmode\nobreak\ :=\leavevmode\nobreak\
\sum_{p\in\\{0,1\\}^{\leq L}:U^{s}(p)=x*}2^{-\ell(p)}\leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\ \text{if}\leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\ \ell(x)\leq n\leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\ \text{and}\leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\ 0\leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\ \text{otherwise}$

is a computable version of the Solomonoff prior and a semimeasure.

We can sample $D^{J}:=(x^{1},...,x^{J})$ from $M_{s,L,n}$ in the same trivial
way as described above for $M$, but now the involved computation is finite.
Note that all sampled strings have length $\leq n$, since $M_{s,L,n}(x):=0$
for $\ell(x)>n$. Consistency of meta-training data is shown next.

######  Proposition 6.

Let now $D^{J}:=(x^{1},...,x^{J})$ be samples from the measure $M_{s,L,n}$.
Then, $\hat{M}_{D^{J}}(x)=\frac{1}{J}\sum_{y\in
D^{J}}[\\![\ell(y)\geq\ell(x)\leavevmode\nobreak\ \wedge\leavevmode\nobreak\
y_{1:\ell(x)}=x]\\!]\leavevmode\nobreak\ \leavevmode\nobreak\
\leavevmode\nobreak\ \longrightarrow\leavevmode\nobreak\ \leavevmode\nobreak\
\leavevmode\nobreak\ M_{s,L,n}(x)\leavevmode\nobreak\ \leavevmode\nobreak\
\leavevmode\nobreak\ \text{for}\leavevmode\nobreak\ \leavevmode\nobreak\
\leavevmode\nobreak\ J\to\infty$.

Since $M(x)=\lim_{s,L,n\to\infty}M_{s,L,n}(x)=\sup_{s,L,n}M_{s,L,n}(x)$, we in
particular have $\hat{M}_{D^{J}}\rightarrow M$ for $s,L,n,J\to\infty$. Note
that $D^{J}$ depends on $s,L,n$, but this can easily be avoided by choosing
$s(j),L(j),n(j)$ to be any functions tending to infinity, and sampling $x^{j}$
from $M_{s(j),L(j),n(j)}(x)$ for $j=1,2,3,...$.

######  Remark 7.

Although $M_{s,L,n}$ is computable, it still suffers from two inconveniences.
First, sampling from it is inefficient because it is a semimeasure and
exhibits a probability gap. Second, we need to differentiate whether programs
halt or end up in a infinite non-printing loop (to fill the probability gap
with “absorbing” tokens when training). We can bypass these inconveniences by
estimating the normalized and computable Solomonoff prior combining
Definitions 3 and 5.

We can estimate the (computable) normalized Solomonoff prior,
$M_{s,L,n}^{norm}(x)$, by the following.

######  Proposition 8.

Using the definitions from Proposition 6 we have that

$\displaystyle\hat{M}_{s,L,n}^{norm}(x_{t}|x_{<t})\leavevmode\nobreak\
=\leavevmode\nobreak\ \frac{\sum_{y\in D^{J}}[\\![\ell(y)\geq
t\leavevmode\nobreak\ \wedge\leavevmode\nobreak\
y_{1:t}=x_{1:t}]\\!]}{\sum_{y\in D^{J}}[\\![\ell(y)\geq t\leavevmode\nobreak\
\wedge\leavevmode\nobreak\ y_{<t}=x_{<t}]\\!]}\leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\ \stackrel{{\scriptstyle
J\to\infty}}{{\longrightarrow}}\leavevmode\nobreak\ \leavevmode\nobreak\
\leavevmode\nobreak\ M_{s,L,n}^{norm}(x_{t}|x_{<t})$

Then, we can take the product over $t=1,...,n$ to obtain
$\hat{M}_{s,L,n}^{norm}(x)\to M_{s,L,n}^{norm}(x)\to M^{norm}(x)$.

Summary. Propositions 4, 6 and 8 state that the data generated by the
Solomonoff Data Generator and their respective variants (computable and
normalized computable) are statistically consistent, and that meta-training on
this data would make an estimator converge to their respective Solomonoff
version (under realizability and learnability assumptions).

###  2.2 Training Models on Solomonoff Data using Fixed-Sequence Lengths

Most neural models (especially Transformers) require training sequences of
fixed length $n$. Due to this, we require a slight modifications to the loss
function for shorter-than-$n$ sequences to maintain convergence to SI. We drop
$s,L,n$ from $M_{s,L,n}^{\cdots}$ since what follows holds for infinite as
well as finite values. We focus on describing the training protocol that
converges to the normalized version of Solomonoff, $M^{norm}$. We refer
readers interested in the standard unnormalized version ($M$) to the Appendix
B.

Normalized Solomonoff $M^{norm}$ with neural networks. To converge to
$M^{norm}$, we pad the $x^{j}$ in $D^{J}$ to length $n$ with arbitrary symbols
from $\mathcal{X}$, and cut the log-loss short at $\ell(x^{j})$. When doing
so, the log-loss takes the form (see Appendix B.1 for derivation that uses
Proposition 8):

$\text{Loss}(\theta)\leavevmode\nobreak\ =\leavevmode\nobreak\
-\sum_{t=1}^{n}\sum_{x_{<t}}\Big{(}\sum_{x_{t}}\hat{M}_{D^{J}}(x_{1:t})\Big{)}\Big{(}\sum_{x_{t}}\hat{M}^{norm}(x_{t}|x_{<t})\log\pi_{\theta}(x_{t}|x_{<t})\Big{)}$
(1)

In this form, it is easy to see how the last bracket, and hence the loss, is
minimized for $\pi_{\theta}(x_{t}|x_{<t})=\hat{M}^{norm}(x_{t}|x_{<t})$, as
desired. By the chain rule this implies that the neural model
$\pi_{\theta}(x)$ converges to $\hat{M}^{norm}(x)$. Note that
$\text{Loss}(\theta)$ does _not_ depend on the padding of $x^{j}$, so any
padding leads to the same gradient and same solution.

Under the (unrealistic) assumptions that the neural model has the capacity to
represent $\hat{M}^{\cdots}$, and the learning algorithm can find the
representation, this (tautologically) implies that the neural model
distribution $\pi_{\theta}$ converges to $\hat{\mu}=\hat{M}^{\cdots}$.
Similarly, if the neural model is trained on $x^{j}$ sampled from
$M_{s(j),L(j),n}^{\cdots}(x)$ for $j=1,2,3,...$, it converges to
$M_{\infty,\infty,n}^{\cdots}$. For a neural model with context length $n$
increasing over time, even $\hat{M}^{\cdots}\to
M^{\cdots}_{\infty,\infty,\infty}$ could be possible. Though theoretically
possible, there are many practical challenges that need to be surmounted to
achieve this, one of them being how to efficiently sample programs.

###  2.3 Solomonoff from Non-Uniform Samples

For practical purposes, sampling from non-uniform (possibly learned)
distribution over programs can be advantageous for efficiency. For our
BrainPhoque language (that we use in our experiments later) it increases the
yield of ‘interesting’ programs by a factor of 137 (see Appendix Table 3).
Below we show this can be done without any concerns on losing universality.

Let $Q$ be a probability measure on $\mathcal{X}^{\infty}$, with shorthand
$Q(q):=Q(\Gamma_{q})$, the $Q$-probability that a sequence starts with $q$,
where
$\Gamma_{q}:=\\{\omega\in\mathcal{X}^{\infty}:q\sqsubseteq\omega\\}=q\mathcal{X}^{\infty}$.
We define the _generalized Solomonoff semimeasure_ as

$\displaystyle M_{T}^{Q}(x)\leavevmode\nobreak\
:=\sum_{q:T(q)=x*\\!\\!\\!\\!}Q(q)\leavevmode\nobreak\ \leavevmode\nobreak\
\leavevmode\nobreak\ \text{with special case}\leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\ M_{U}(x)\leavevmode\nobreak\
:=\sum_{q:U(q)=x*\\!\\!\\!\\!}2^{-\ell(q)}$

for a universal TM $T=U$ and unbiased coin flips $Q(q)=2^{-\ell(q)}$. $M_{U}$
is strongly universal in the sense that it is a Bayesian mixture over all
lower semi-computable semimeasures (Wood et al., 2011). Next, we show that
under very mild conditions on $Q$, $M_{U}^{Q}$ is also universal. This finding
is similar to (Sterkenburg, 2017), but our independently discovered proof is
shorter and more self-contained.

######  Theorem 9 (Universality of generalized Solomonoff semimeasures).

$M_{U}^{Q}(x)$ is strongly universal, provided $Q$ is a computable measure and
$Q(q)>0\leavevmode\nobreak\ \forall q\in\mathcal{X}^{*}$ and $Q(q_{1:n})\to 0$
for $n\to\infty$. More precisely, for all universal monotone TM $U$ and all
$Q$ with the above properties, there exists a universal MTM $V$ (as
constructed in the proof) s.th. $M_{U}^{Q}(x)=M_{V}(x)\leavevmode\nobreak\
\forall x$. Proof in Appendix C.

Note on the assumptions above. We assumed an infinite number of data points
and universality (and learnablity) of the approximator, which are difficult to
obtain in practice and diminish the relevance of inductive biases of neural
models. For finite data, however, inductive biases are important for strong
generalization. We leave out of the scope of the paper the theoretical work on
the effect of the inductive bias and universality of neural models and simply
provide experimental evidence of neural network performance in the next
section.

##  3 Experimental Methodology

Figure 2: Evaluation on VOMS data. Left: Example sequence and highly
overlapped predictions of Transformer-L (red) and Bayes-optimal CTW predictor
(blue). Lower panels show instantaneous and cumulative regret w.r.t. the
ground-truth. Middle: Mean cumulative regret over $6$k sequences (length
$256$, max. CTW tree depth $24$, in-distribution) for different networks ($3$
seeds) and sizes (S, M, L). Larger models perform better for all
architectures, and the Transformer-L and LSTM-L match the optimal CTW
predictor. Right: Length generalization ($1024$ steps). LSTMs generalize to
longer length, whereas Transformers do not.

We aim to evaluate various neural architectures and sizes trained on UTM and
two other types of algorithmically generated data for comparison and analysis.

Variable-order Markov Sources (VOMS). A $k$-Markov model assigns probabilities
to a string of characters by, at any step $t$, only using the last $k$
characters to output the next character probabilities. A VOMS is a Markov
model where the value of $k$ is variable and it is obtained using a tree of
non-uniform depth. A tree here is equivalent to a program that generates data.
We sample trees and meta-train on the generated data. We consider _binary_
VOMS where a Bayes-optimal predictor exists: the Context Tree Weighting (CTW)
predictor (Willems et al., 1995, 1997), to which we compare our models to. CTW
is only universal w.r.t. $n$-Markov sources, and not w.r.t. all computable
functions like SI. See Appendix D.2 for more intuition on VOMS, how we
generate the data and how to compute the CTW Bayes-optimal predictor.

Chomsky Hierarchy (CH) Tasks. We take the $15$ algorithmic tasks (e.g.
arithmetic, reversing strings) from Deletang et al. (2022) lying on different
levels of the Chomsky hierarchy (see Appendix D.3 for a description of all
tasks). These tasks are useful for comparison and for assessing the
algorithmic power of our models. In contrast to Deletang et al. (2022), in
which they train on _individual_ tasks, we are interested in meta-training on
all tasks _simultaneously_. We make sure that all tasks use the same alphabet
$\mathcal{X}$ (expanding the alphabet of tasks with smaller alphabets). We do
not consider transduction as in Deletang et al. (2022) but sequence
prediction, thus we concatenate inputs and outputs with additional delimiter
tokens i.e. for $\\{(x_{i}\in\mathcal{X},y_{i}\in\mathcal{X})\\}_{i=1}^{I}$
and delimiters ‘,’ and ‘;’, we construct sequences of the form
$z:=(x_{1},y_{1};x_{2},y_{2};\dots x_{n},y_{n};\dots)$. We evaluate our models
using the regret (and accuracy) _only_ on the output symbols, masking the
inputs because they are usually random and non-informative of task
performance. Denoting $\mathcal{O}_{z}$ the set of outputs time-indices, we
compute accuracy for trajectory $z$ as
$A(z):=\frac{1}{|\mathcal{O}_{z}|}\sum_{t\in\mathcal{O}_{z}}[\\![\operatorname*{arg\,max}_{y}\pi_{\theta}(y|z_{<t})=z_{t}]\\!]$.
See Appendix D.3 for details.

Universal Turing Machine Data. Following Sections 2.1 and 2.2, we generate
random programs (encoding any structured sequence generation process) and run
them in our UTM to generate the outputs. A program could, in principle,
generate the image of a cow, a chess program, or the books of Shakespeare, but
of course, these programs are extremely unlikely to be sampled (see Figure 6
in the Appendix for exemplary outputs). As a choice of UTM, we constructed a
variant of the BrainF*ck UTM (Müller, 1993), which we call BrainPhoque, mainly
to help with the sampling process and to ensure that all sampled programs are
valid. We set output symbols alphabet size to $|\mathcal{X}|=17$, equal to the
Chomsky tasks, to enable task-transfer evaluation. BrainPhoque has a single
working tape and a write-only output tape. It has $7$ instructions to move the
working tape pointer (WTP), de/increment the value under the WTP (the
_datum_), perform jumps and append the datum to the output. We skip imbalanced
brackets to make all programs valid. While it slightly changes the program
distribution, this is not an issue according to Theorem 9: each valid program
has a non-zero probability to be sampled. Programs are generated and run at
the same time, as described in Sections 2.1 and 2.2, for $s=1000$ steps with
$200$ memory cells, with a maximum output length of $n=256$ symbols. Ideally,
we should use SI as the optimal baseline comparison but since it is
uncomputable and intractable, we calculate a (rather loose, but non-trivial)
upper bound on the log-loss by using the prior probability of shortened
programs (removing unnecessary brackets or self-canceling instructions) that
generate the outputs. See Appendix E for a full description of BrainPhoque and
our sampling procedure.

Neural Predictors. Our neural models $\pi_{\theta}$ sequentially observe
symbols $x_{<t}$ from the data generating source and predict the next-symbol
probabilities $\pi_{\theta}(\cdot|x_{<t})$. We train our models using the log-
loss
$\text{Loss}(\theta):=-\frac{1}{n}\sum_{t=1}^{n}\log\pi_{\theta}(x_{t}|x_{<t})$,
therefore maximizing lossless compression of input sequences (Delétang et al.,
2023). We use stochastic gradient descent with the ADAM optimizer (Kingma and
Ba, 2014). We train for $500$K iterations with batch size $128$, sequence
length $256$, and learning rate $10^{-4}$. On the UTM data source, we cut the
log-loss to approximate the normalized version of SI (see Section 2.2). We
evaluate the following architectures: RNNs, LSTMs, Stack-RNNs, Tape-RNNs and
Transformers. We note that Stack-RNNs (Joulin and Mikolov, 2015) and Tape-RNNs
(Deletang et al., 2022) are RNNs augmented with a stack and tape memory,
respectively, which stores and manipulate symbols. This external memory should
help networks to predict better, as showed in Deletang et al. (2022). We
consider three model sizes (S, M and L) for each architecture by increasing
the width and depth simultaneously. We train $3$ parameter initialization
seeds per model variation. See Appendix D.1 for all architecture details.

Evaluation procedure. Our main evaluation metric is the _expected
instantaneous regret_ ,
$R_{\pi\mu}(t):=\mathbb{E}_{x_{t}\sim\mu}\left[\log\mu(x_{t}\mid
x_{<t})-\log\pi(x_{t}\mid x_{<t})\right]$ (at time $t$), and _cumulative
expected regret_ , $R_{\pi\mu}^{T}:=\sum_{t=1}^{T}R_{\pi\mu}(t)$, where $\pi$
is the model and $\mu$ the ground-truth source. The lower the regret the
better. We evaluate our neural models on $6$k sequences of length $256$, which
we refer as _in-distribution_ (same length as used for training) and of length
$1024$, referred as _out-of-distribution_.

##  4 Results

Figure 3: Evaluation on $6$k sequences from the Chomsky hierarchy tasks ($400$
per task). As the model size increases, cumulative regret (Left) and accuracy
(Middle) improve across all architectures. Overall, the Transformer-L achieves
the best performance by a margin. Right: Length generalization ($1024$ steps).
Detailed results per task are in Figure 8 on the Appendix.

Variable-order Markov Source (VOMS) Results. In Figure 2 (Left) we show an
example trajectory from VOMS data-source of length $256$ with the true samples
(blue dots), ground truth (gray), Transformer-L (red) and CTW (blue)
predictions. As we can see, the predictions of the CTW predictor and the
Transformer-L are overlapping, suggesting that the Transformer is implementing
a Bayesian mixture over programs/trees like the CTW does, which is necessary
to perform SI. In the second and third panels the instantaneous regret and the
cumulative regret also overlap. Figure 2 (Middle) shows the cumulative regret
of all neural predictors evaluated in-distribution. First, we observe that as
model size increases (from S, M, to L) the cumulative regret decreases. The
best model is the Transformer-L achieving optimal performance, whereas the
worst models are the RNNs and the Tape-RNNs. The latter model likely could not
successfully leverage its external memory. Note how LSTM-L achieves close to
optimal performance. On the Right we show the out-of-distribution performance
showing how transformers fail on length-generalization, whereas LSTMs perform
the best. To better understand where our models struggle, we show in the
Appendix F, Figures 7(c) and 7(d), the cumulative regret averaged across
trajectories from different CTW tree depths and context lengths. Models
perform uniformly for all tree-depths and struggle on mid-sized context-
lengths.

Chomsky Hierarchy Results. In Figure 3 (Left) we show the in-distribution
performance of all our models trained on the Chomsky hierarchy tasks by means
of cumulative regret and accuracy. Overall, the Transformer-L achieves the
best performance by a margin. This suggests that our models, specially
Transformers, have the capability of algorithmic reasoning to some extent. On
the Right we show the length-generalization capabilities of models, showing
how Transformers fail to generalize to longer lengths. In the Appendix (Figure
8) we show the results for each task individually.

Universal Turing Machine Results. Figure 4 (Left) shows the mean cumulative
regret on the UTM task with the (loose) Solomonoff Upper Bound (UB) as a non-
trivial baseline (see Section 3 for its description). In the Middle we show
how all models achieve fairly good accuracy. This shows how our models are
capable of learning a broad set of patterns present in the data (see example
UTM trajectories in appendix Figure 6). In general, larger architectures
attain lower cumulative regret and all models beat the Solomonoff upper bound.
Performing better than the bound is non-trivial since the upper-bound is
computed using the underlying program that generated the outputs whereas the
neural models do not have this information. In Figure 9 (in the Appendix) we
show the cumulative regret against program length and, as expected, observe
that the longer the underlying program of a sequence the higher the cumulative
regret of our models, suggesting a strong correlation between program length
and prediction difficulty. Remarkably, in Figure 5 we see that the Transformer
networks trained on UTM data exhibit the most transfer to the Chomsky tasks
and, LSTMs transfer the most to the VOMS task (compare to the ‘naive’ random
predictor). For the VOMS, we re-trained the LSTM and Transformer models with
the BrainPhoque UTM setting the alphabet size to $2$ matching our VOMS task to
enable comparison. All transfer results suggest that UTM data contains enough
transferable patterns for these tasks.

Figure 4: Evaluation on the UTM data generator with $6$k sequences. Left: The
larger the architecture the lower the cumulative regret. We see better
performance than the non-trivial baseline Solomonoff Upper Bound (UB). Middle:
The mean accuracy on UTM data shows the models can quickly learn UTM patterns.
Right: Length generalization ($1024$ steps). Detailed results per program
length are in Figure 9.

Figure 5: Transfer learning from _UTM-trained models_ on $3$k trajectories.
Mean cumulative regret (Left) and accuracy (Middle-Left) of neural models
trained on UTM data evaluated against the tasks of the Chosmky hierarchy. We
observe a small increase in accuracy (transfer) from the Transformer models.
Transfer to CTW is shown in the right two panels: Middle-Right: mean
cumulative regret, Right: mean accuracy; ‘Naive’ is a random uniform
predictor.

##  5 Discussion and Conclusions

Large Language Models (LLMs) and Solomonoff Induction. The last few years the
ML community has witnessed the training of enormous models on massive
quantities of diverse data (Kenton and Toutanova, 2019; Hoffmann et al.,
2022). This trend is in line with the premise of our paper, i.e. to achieve
increasingly universal models one needs large architectures and large
quantities of diverse data. LLMs have been shown to have impressive in-context
learning capabilities (Kenton and Toutanova, 2019; Chowdhery et al., 2022).
LLMs pretrained on long-range coherent documents can learn new tasks from a
few examples by inferring a shared latent concept (Xie et al., 2022; Wang et
al., 2023). They can do so because in-context learning does implicit Bayesian
inference (in line with our CTW experiments) and builds world representations
and algorithms (Li et al., 2023a, b) (necessary to perform SI). In fact, one
could argue that the impressive in-context generalization capabilities of LLMs
is a sign of a rough approximation of Solomonoff induction. The advantage of
pre-trained LLMs compared to our method (training on universal data) is that
LLM data (books, code, online conversations etc.) is generated by humans, and
thus very well aligned with the tasks we (humans) want to solve; whereas our
UTMs do not necessarily assign high probability to human tasks.

Learning the UTM. Theorem 9 of our paper (and (Sterkenburg, 2017)) opens the
path for modifying/learning the program distribution of a UTM while
maintaining the universality property. This is of practical importance since
we would prefer distributions that assign high probability to programs
relevant for human tasks. Similarly, the aim of Sunehag and Hutter (2014) is
to directly learn a UTM aligned to problems of interest. A good UTM or program
distribution would contribute to having better synthetic data generation used
to improve our models. This would be equivalent to data-augmentation technique
so successfully used in the machine learning field (Perez and Wang, 2017;
Lemley et al., 2017; Kataoka et al., 2020). In future work, equipped with our
Theorem 9, we plan study optimizations to the sampling process from UTMs to
produce more human-aligned outputs.

Increasingly Universal Architectures. The output of the UTM $U^{s}(p)$ (using
program $p$) requires at maximum $s$ computational steps. Approximating
$M_{s,L,n}$ would naively require wide networks (to represent many programs in
parallel) of $s$-depth and context length $n$. Thus bigger networks would
better approximate stronger SI approximations. If computational patterns can
be reused, depth could be smaller than $s$. Transformers seem to exhibit
reusable “shortcuts” thereby representing all automata of length $T$ in
$O(\log T)$-depth (Liu et al., 2023). An alternative way to increase the
amount of serial computations is with chain-of-thought (Wei et al., 2022) (see
Hahn and Goyal (2023) for theoretical results). When data is limited,
inductive biases are important for generalization. Luckily it seems neural
networks have an implicit inductive bias towards simple functions at
initialization (Dingle et al., 2018; Valle-Perez et al., 2018; Mingard et al.,
2023) compatible with Kolmogorov complexity, which is greatly convenient when
trying to approximate SI in the finite-data regime.

Limitations. Given the empirical nature of our results, we cannot guarantee
that our neural networks mimic SI’s universality. Solomonoff Induction is
uncomputable/undecidable and one would need infinite time to exactly match it
in the limit. However, our theoretical results establish that good
approximations are obtainable, in principle, via meta-training; whereas our
empirical results show that is possible to make practical progress in that
direction, though many questions remain open, e.g., how to construct efficient
relevant universal datasets for meta-learning, and how to obtain easily-
trainable universal architectures.

Conclusion. We aimed at using meta-learning as driving force to approximate
Solomonoff Induction. For this we had to carefully specify the data generation
process and the training loss so that the convergence (to various versions of
SI) is attained in the limit. Our experiments on the three different
algorithmic data-sources tell that: neural models can implement algorithms and
Bayesian mixtures, and that larger models attain increased performance.
Remarkably, networks trained on the UTM data exhibit transfer to the other
domains suggesting they learned a broad set of transferable patterns. We
believe that we can improve future sequence models by scaling our approach
using UTM data and mixing it with existing large datasets.

Reproducibility Statement. On the theory side, we wrote all proofs in the
Appendix. For data generation, we fully described the variable-order Markov
sources in the Appendix; we used the open-source repository
https://github.com/google-deepmind/neural_networks_chomsky_hierarchy for the
Chomsky tasks and fully described our UTM in the Appendix. We used the same
architectures as Deletang et al. (2022) (which can be found in the same open-
source repository) with modifications described in the Appendix. For training
our models we used JAX https://github.com/google/jax.

## References

  * Böhm (1964) C. Böhm.  On a family of turing machines and the related programming language.  _ICC bulletin_ , 3:185–194, 1964.
  * Catt et al. (2024) E. Catt, D. Quarel, and M. Hutter.  _An Introduction to Universal Artificial Intelligence_.  Chapman & Hall/CRC Artificial Intelligence and Robotics Series. Taylor and Francis, 2024.  ISBN 9781032607153.  URL http://www.hutter1.net/ai/uaibook2.htm.  400+ pages, http://www.hutter1.net/ai/uaibook2.htm.
  * Chen et al. (2017) Y. Chen, S. Gilroy, A. Maletti, J. May, and K. Knight.  Recurrent neural networks as weighted language recognizers.  _arXiv preprint arXiv:1711.05408_ , 2017.
  * Chomsky (1956) N. Chomsky.  Three models for the description of language.  _IRE Transactions on information theory_ , 2(3):113–124, 1956.
  * Chowdhery et al. (2022) A. Chowdhery, S. Narang, J. Devlin, M. Bosma, G. Mishra, A. Roberts, P. Barham, H. W. Chung, C. Sutton, S. Gehrmann, et al.  Palm: Scaling language modeling with pathways.  _arXiv preprint arXiv:2204.02311_ , 2022.
  * Deletang et al. (2022) G. Deletang, A. Ruoss, J. Grau-Moya, T. Genewein, L. K. Wenliang, E. Catt, C. Cundy, M. Hutter, S. Legg, J. Veness, et al.  Neural networks and the chomsky hierarchy.  In _The Eleventh International Conference on Learning Representations_ , 2022.
  * Delétang et al. (2023) G. Delétang, A. Ruoss, P.-A. Duquenne, E. Catt, T. Genewein, C. Mattern, J. Grau-Moya, L. K. Wenliang, M. Aitchison, L. Orseau, M. Hutter, and J. Veness.  Language modeling is compression, 2023.
  * Dingle et al. (2018) K. Dingle, C. Q. Camargo, and A. A. Louis.  Input–output maps are strongly biased towards simple outputs.  _Nature communications_ , 9(1):761, 2018.
  * Elman (1990) J. L. Elman.  Finding structure in time.  _Cogn. Sci._ , 1990.
  * Filan et al. (2016) D. Filan, J. Leike, and M. Hutter.  Loss bounds and time complexity for speed priors.  In _Artificial Intelligence and Statistics_ , pages 1394–1402. PMLR, 2016.
  * Genewein et al. (2023) T. Genewein, G. Delétang, A. Ruoss, L. K. Wenliang, E. Catt, V. Dutordoir, J. Grau-Moya, L. Orseau, M. Hutter, and J. Veness.  Memory-based meta-learning on non-stationary distributions.  _International Conference on Machine Learning_ , 2023.
  * Hahn and Goyal (2023) M. Hahn and N. Goyal.  A theory of emergent in-context learning as implicit structure induction.  _arXiv preprint arXiv:2303.07971_ , 2023.
  * Hochreiter and Schmidhuber (1997) S. Hochreiter and J. Schmidhuber.  Long short-term memory.  _Neural Comput._ , 1997.
  * Hoffmann et al. (2022) J. Hoffmann, S. Borgeaud, A. Mensch, E. Buchatskaya, T. Cai, E. Rutherford, D. d. L. Casas, L. A. Hendricks, J. Welbl, A. Clark, et al.  Training compute-optimal large language models.  _arXiv preprint arXiv:2203.15556_ , 2022.
  * Hospedales et al. (2021) T. Hospedales, A. Antoniou, P. Micaelli, and A. Storkey.  Meta-learning in neural networks: A survey.  _IEEE transactions on pattern analysis and machine intelligence_ , 44(9):5149–5169, 2021.
  * Hutter (2004) M. Hutter.  _Universal artificial intelligence: Sequential decisions based on algorithmic probability_.  Springer Science & Business Media, 2004.
  * Hutter (2006/2020) M. Hutter.  Human knowledge compression prize, 2006/2020.  open ended, http://prize.hutter1.net/.
  * Hutter (2007) M. Hutter.  On universal prediction and Bayesian confirmation.  _Theoretical Computer Science_ , 384(1):33–48, 2007.  ISSN 0304-3975.  10.1016/j.tcs.2007.05.016.  URL http://arxiv.org/abs/0709.1516.
  * Hutter (2017) M. Hutter.  Universal learning theory.  In C. Sammut and G. Webb, editors, _Encyclopedia of Machine Learning and Data Mining_ , pages 1295–1304. Springer, 2nd edition, 2017.  ISBN 978-1-4899-7686-4.  10.1007/978-1-4899-7687-1_867.  URL http://arxiv.org/abs/1102.2467.
  * Hutter et al. (2007) M. Hutter, S. Legg, and P. M. B. Vitányi.  Algorithmic probability.  _Scholarpedia_ , 2(8):2572, 2007.  ISSN 1941-6016.  10.4249/scholarpedia.2572.
  * Joulin and Mikolov (2015) A. Joulin and T. Mikolov.  Inferring algorithmic patterns with stack-augmented recurrent nets.  In _Advances in Neural Information Processing Systems 28_ , 2015.
  * Kataoka et al. (2020) H. Kataoka, K. Okayasu, A. Matsumoto, E. Yamagata, R. Yamada, N. Inoue, A. Nakamura, and Y. Satoh.  Pre-training without natural images.  In _Proceedings of the Asian Conference on Computer Vision_ , 2020\.
  * Kenton and Toutanova (2019) J. D. M.-W. C. Kenton and L. K. Toutanova.  Bert: Pre-training of deep bidirectional transformers for language understanding.  In _Proceedings of NAACL-HLT_ , pages 4171–4186, 2019.
  * Kingma and Ba (2014) D. P. Kingma and J. Ba.  Adam: A method for stochastic optimization.  _arXiv preprint arXiv:1412.6980_ , 2014.
  * Lattimore et al. (2011) T. Lattimore, M. Hutter, and V. Gavane.  Universal prediction of selected bits.  In _Algorithmic Learning Theory: 22nd International Conference, ALT 2011, Espoo, Finland, October 5-7, 2011. Proceedings 22_ , pages 262–276. Springer, 2011.
  * Lemley et al. (2017) J. Lemley, S. Bazrafkan, and P. Corcoran.  Smart augmentation learning an optimal data augmentation strategy.  _Ieee Access_ , 5:5858–5869, 2017.
  * Li et al. (2023a) K. Li, A. K. Hopkins, D. Bau, F. Viégas, H. Pfister, and M. Wattenberg.  Emergent world representations: Exploring a sequence model trained on a synthetic task.  In _The Eleventh International Conference on Learning Representations_ , 2023a.  URL https://openreview.net/forum?id=DeG07_TcZvT.
  * Li and Vitanyi (1992) M. Li and P. M. Vitanyi.  Inductive reasoning and kolmogorov complexity.  _Journal of Computer and System Sciences_ , 44(2):343–384, 1992.
  * Li et al. (2019) M. Li, P. Vitányi, et al.  _An introduction to Kolmogorov complexity and its applications_.  Springer, 4th edition, 2019.
  * Li et al. (2023b) Y. Li, M. E. Ildiz, D. Papailiopoulos, and S. Oymak.  Transformers as algorithms: Generalization and implicit model selection in in-context learning.  _arXiv preprint arXiv:2301.07067_ , 2023b.
  * Liu et al. (2023) B. Liu, J. T. Ash, S. Goel, A. Krishnamurthy, and C. Zhang.  Transformers learn shortcuts to automata.  In _The Eleventh International Conference on Learning Representations_ , 2023.  URL https://openreview.net/forum?id=De4FYqjFueZ.
  * Mali et al. (2023) A. Mali, A. Ororbia, D. Kifer, and L. Giles.  On the computational complexity and formal hierarchy of second order recurrent neural networks.  _arXiv preprint arXiv:2309.14691_ , 2023.
  * Mikulik et al. (2020) V. Mikulik, G. Delétang, T. McGrath, T. Genewein, M. Martic, S. Legg, and P. Ortega.  Meta-trained agents implement bayes-optimal agents.  _Advances in neural information processing systems_ , 33:18691–18703, 2020.
  * Mingard et al. (2023) C. Mingard, H. Rees, G. Valle-Pérez, and A. A. Louis.  Do deep neural networks have an inbuilt occam’s razor?  _arXiv preprint arXiv:2304.06670_ , 2023.
  * Müller (1993) U. Müller.  Brainf*ck.  https://esolangs.org/wiki/Brainfuck, 1993.  [Online; accessed 21-Sept-2023].
  * Ortega et al. (2019) P. A. Ortega, J. X. Wang, M. Rowland, T. Genewein, Z. Kurth-Nelson, R. Pascanu, N. Heess, J. Veness, A. Pritzel, P. Sprechmann, et al.  Meta-learning of sequential strategies.  _arXiv preprint arXiv:1905.03030_ , 2019.
  * Perez and Wang (2017) L. Perez and J. Wang.  The effectiveness of data augmentation in image classification using deep learning.  _arXiv preprint arXiv:1712.04621_ , 2017.
  * Rathmanner and Hutter (2011) S. Rathmanner and M. Hutter.  A philosophical treatise of universal induction.  _Entropy_ , 13(6):1076–1136, 2011.
  * Schmidhuber (2002) J. Schmidhuber.  The speed prior: A new simplicity measure yielding near-optimal computable predictions.  In _Proc. 15th Conf. on Computational Learning Theory (COLT’02)_ , volume 2375 of _LNAI_ , pages 216–228, Sydney, Australia, 2002\. Springer.
  * Sipser (2012) M. Sipser.  _Introduction to the Theory of Computation_.  Course Technology Cengage Learning, Boston, MA, 3rd ed edition, 2012\.  ISBN 978-1-133-18779-0.
  * Solomonoff (1964a) R. J. Solomonoff.  A formal theory of inductive inference. part i.  _Information and control_ , 7(1):1–22, 1964a.
  * Solomonoff (1964b) R. J. Solomonoff.  A formal theory of inductive inference. part ii.  _Information and control_ , 7(2):224–254, 1964b.
  * Sterkenburg (2017) T. F. Sterkenburg.  A generalized characterization of algorithmic probability.  _Theory of Computing Systems_ , 61:1337–1352, 2017.
  * Stogin et al. (2020) J. Stogin, A. Mali, and C. L. Giles.  A provably stable neural network turing machine.  _arXiv preprint arXiv:2006.03651_ , 2020.
  * Sunehag and Hutter (2013) P. Sunehag and M. Hutter.  Principles of solomonoff induction and aixi.  In _Algorithmic Probability and Friends. Bayesian Prediction and Artificial Intelligence: Papers from the Ray Solomonoff 85th Memorial Conference, Melbourne, VIC, Australia, November 30–December 2, 2011_ , pages 386–398. Springer, 2013.
  * Sunehag and Hutter (2014) P. Sunehag and M. Hutter.  Intelligence as inference or forcing Occam on the world.  In _Proc. 7th Conf. on Artificial General Intelligence (AGI’14)_ , volume 8598 of _LNAI_ , pages 186–195, Quebec City, Canada, 2014\. Springer.  ISBN 978-3-319-09273-7.  10.1007/978-3-319-09274-4_18.
  * Suzgun et al. (2019) M. Suzgun, S. Gehrmann, Y. Belinkov, and S. M. Shieber.  Memory-augmented recurrent neural networks can learn generalized dyck languages.  _CoRR_ , 2019.
  * Valle-Perez et al. (2018) G. Valle-Perez, C. Q. Camargo, and A. A. Louis.  Deep learning generalizes because the parameter-function map is biased towards simple functions.  _arXiv preprint arXiv:1805.08522_ , 2018.
  * Vaswani et al. (2017) A. Vaswani, N. Shazeer, N. Parmar, J. Uszkoreit, L. Jones, A. N. Gomez, L. Kaiser, and I. Polosukhin.  Attention is all you need.  In _Advances in Neural Information Processing Systems 30_ , 2017.
  * Veness et al. (2012) J. Veness, P. Sunehag, and M. Hutter.  On ensemble techniques for aixi approximation.  In _International Conference on Artificial General Intelligence_ , pages 341–351. Springer, 2012.
  * Wang et al. (2023) X. Wang, W. Zhu, and W. Y. Wang.  Large language models are implicitly topic models: Explaining and finding good demonstrations for in-context learning.  _arXiv preprint arXiv:2301.11916_ , 2023.
  * Wei et al. (2022) J. Wei, X. Wang, D. Schuurmans, M. Bosma, F. Xia, E. Chi, Q. V. Le, D. Zhou, et al.  Chain-of-thought prompting elicits reasoning in large language models.  _Advances in Neural Information Processing Systems_ , 35:24824–24837, 2022.
  * Willems et al. (1997) F. Willems, Y. Shtarkov, and T. Tjalkens.  Reflections on “the context tree weighting method: Basic properties”.  _Newsletter of the IEEE Information Theory Society_ , 47(1), 1997.
  * Willems (1998) F. M. Willems.  The context-tree weighting method: Extensions.  _IEEE Transactions on Information Theory_ , 44(2):792–798, 1998.
  * Willems et al. (1995) F. M. Willems, Y. M. Shtarkov, and T. J. Tjalkens.  The context-tree weighting method: Basic properties.  _IEEE transactions on information theory_ , 41(3):653–664, 1995.
  * Wood et al. (2011) I. Wood, P. Sunehag, and M. Hutter.  (Non-)equivalence of universal priors.  In _Proc. Solomonoff 85th Memorial Conference_ , volume 7070 of _LNAI_ , pages 417–425, Melbourne, Australia, 2011. Springer.  ISBN 978-3-642-44957-4.  10.1007/978-3-642-44958-1_33.  URL http://arxiv.org/abs/1111.3854.
  * Wood et al. (2013) I. Wood, P. Sunehag, and M. Hutter.  (non-) equivalence of universal priors.  In _Algorithmic Probability and Friends. Bayesian Prediction and Artificial Intelligence: Papers from the Ray Solomonoff 85th Memorial Conference, Melbourne, VIC, Australia, November 30–December 2, 2011_ , pages 417–425. Springer, 2013.
  * Xie et al. (2022) S. M. Xie, A. Raghunathan, P. Liang, and T. Ma.  An explanation of in-context learning as implicit bayesian inference.  In _International Conference on Learning Representations_ , 2022.  URL https://openreview.net/forum?id=RdJVFCHjUMI.

##  6 Appendix

##  Appendix A Solomonoff samples

#### Sampling from semimeasures.

We can sample strings from a semimeasure $\mu$ as follows: Start with the
empty string $x=\epsilon$.
With probability $\mu(a|x):=\mu(xa)/\mu(x)$ extend $x\leftarrow xa$ for
$a\in\mathcal{X}$. Repeat.
With probability $1-\sum_{a\in\mathcal{X}}\mu(a|x)$ return $x$.

Let $D:=(x^{1},...,x^{J})$ be $J$ (in)finite sequences sampled from $\mu$. If
we only have these samples, we can estimate $\mu$ as follows:

$\displaystyle\hat{\mu}_{D}(x)\leavevmode\nobreak\ :=\leavevmode\nobreak\
\frac{1}{|D|}\sum_{y\in D}[\\![\ell(y)\geq\ell(x)\leavevmode\nobreak\
\wedge\leavevmode\nobreak\ y_{1:\ell(x)}=x]\\!]\leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\ \stackrel{{\scriptstyle
w.p.1}}{{\longrightarrow}}\leavevmode\nobreak\ \leavevmode\nobreak\
\leavevmode\nobreak\ \mu(x)\leavevmode\nobreak\ \leavevmode\nobreak\
\leavevmode\nobreak\ \text{for}\leavevmode\nobreak\ \leavevmode\nobreak\
\leavevmode\nobreak\ |D|\to\infty$ (2)

_Proof:_ Let $D_{x}:=(y\in D:\ell(y)\geq\ell(x)\leavevmode\nobreak\
\wedge\leavevmode\nobreak\ y_{1:\ell(y)}=x)$ be the elements in $D$ that start
with $x$. Since $x^{j}$ are sampled i.i.d. from $\mu$, the law of large
numbers implies $|D_{x}|/|D|\to\mu(x)$ for $J\to\infty$.∎

#### Limit normalization.

A simple way of normalization is

$\displaystyle\widetilde{M}_{s,L,n}(x_{1:t})\leavevmode\nobreak\
:=\leavevmode\nobreak\
\frac{\sum_{x_{t+1:n}}M_{s,L,n}(x_{1:n})}{\sum_{x_{1:n}}M_{s,L,n}(x_{1:n})}\leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\ \text{for}\leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\ t\leq n\leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\ \text{and}\leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\ 0\leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\ \text{else}$

This is a proper measure for sequences up to length $n$. Sampling from it is
equivalent to sampling from $M_{s,L,n}$ but discarding all sequences shorter
than $n$. Let $\widetilde{D}:=(x^{j}\in D^{J}:\ell(x^{j})\geq n)$. Then

$\displaystyle\hat{\widetilde{M}}_{\widetilde{D}}(x)\leavevmode\nobreak\
=\leavevmode\nobreak\
\frac{1}{|\widetilde{D}|}\sum_{y\in\widetilde{D}}[\\![y_{1:\ell(x)}=x]\\!]\leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\ \longrightarrow\leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\ M(x)\leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\ \text{for}\leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\ s,L,n,J\to\infty$

_Proof:_ First, $|\widetilde{D}|/|D|$ is the relative fraction of sequences
that have length $n$, and $\sum_{x_{1:n}}M_{s,L,n}(x_{1:n})$ is the
probability that a sequence has length $n$, hence the former converges to the
latter for $J\to\infty$. Second,

$\displaystyle\hat{\widetilde{M}}_{\widetilde{D}}(x_{1:n})\leavevmode\nobreak\
$ $\displaystyle=\leavevmode\nobreak\
\frac{1}{|\widetilde{D}|}\sum_{y\in\widetilde{D}}[\\![y_{1:\ell(x)}=x_{1:n}]\\!]\leavevmode\nobreak\
=\leavevmode\nobreak\ \frac{|D|}{|\widetilde{D}|}\frac{1}{|D|}\sum_{y\in
D}[\\![\ell(y)\geq n\leavevmode\nobreak\ \wedge\leavevmode\nobreak\
y_{1:\ell(x)}=x_{1:n}]\\!]$ $\displaystyle=\leavevmode\nobreak\
\frac{|D|}{|\widetilde{D}|}\hat{M}_{D^{J}}(x_{1:n})\leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\ \stackrel{{\scriptstyle
J\to\infty}}{{\longrightarrow}}\leavevmode\nobreak\ \leavevmode\nobreak\
\leavevmode\nobreak\
\frac{M_{s,L,n}(x_{1:n})}{\sum_{x_{1:n}}M_{s,L,n}(x_{1:n})}\leavevmode\nobreak\
=\leavevmode\nobreak\ \widetilde{M}_{s,L,n}(x_{1:n})$

Third, take the sum $\sum_{x_{t+1:n}}$ on both sides, and finally the limit
$s,L,n\to\infty$ and set $x=x_{1:t}$. ∎

A disadvantage of this normalization scheme is that the probability of a
sequence $x$ depends on $n$ even if $\ell(x)<n$, while $M_{s,L,n}(x)$ and
$M_{\cdots}^{norm}(x)$ below are essentially independent of $n$.

See 4

_Proof:_ Let $D_{x}:=(y\in D:\ell(y)\geq\ell(x)\leavevmode\nobreak\
\wedge\leavevmode\nobreak\ y_{1:\ell(y)}=x)$ be the elements in $D$ that start
with $x$. Since $x^{j}$ are sampled i.i.d. from $\mu$, the law of large
numbers implies $|D_{x}|/|D|\to\mu(x)$ for $J\to\infty$.∎

See 6 _Proof:_ It follows directly from Proposition 4.

See 8

_Proof:_ For $x=x_{<t}$ and $a=x_{t}$, we have

$\displaystyle\sum_{a\in\mathcal{X}}\hat{M}_{D^{J}}(xa)\leavevmode\nobreak\ $
$\displaystyle=\leavevmode\nobreak\ \frac{1}{J}\sum_{a}\sum_{y\in
D^{J}}[\\![\ell(y)\geq\ell(xa)\leavevmode\nobreak\ \wedge\leavevmode\nobreak\
y_{1:\ell(xa)}=xa]\\!]$ $\displaystyle=\leavevmode\nobreak\
\frac{1}{J}\sum_{y\in D^{J}}[\\![\ell(y)\geq t\leavevmode\nobreak\
\wedge\leavevmode\nobreak\ \exists a:y_{1:t}=xa]\\!]$ hence
$\displaystyle\leavevmode\nobreak\
\hat{M}_{s,L,n}^{norm}(a|x)\leavevmode\nobreak\ =\leavevmode\nobreak\
\frac{\hat{M}_{D^{J}}(xa)}{\sum_{a}\hat{M}_{D^{J}}(xa)}\leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\ \stackrel{{\scriptstyle
J\to\infty}}{{\longrightarrow}}\leavevmode\nobreak\ \leavevmode\nobreak\
\leavevmode\nobreak\
\frac{M_{s,L,n}(ax)}{\sum_{a}M_{s,L,n}(ax)}\leavevmode\nobreak\
=\leavevmode\nobreak\ M_{s,L,n}^{norm}(a|x)$ (3)

∎

##  Appendix B Training with Transformers

#### Using Transformers for estimating $M$.

Most Transformer implementations require sequences of fixed length (say) $n$.
We can mimic shorter sequences by introducing a special absorbing symbol
$\bot\not\in\mathcal{X}$, and pad all sequences $x^{j}$ shorter than $n$ with
$\bot$s. We train the Transformer on these (padded) sequences with the log-
loss. Under the (unrealistic) assumptions that the Transformer has the
capacity to represent $\hat{M}_{\cdots}$, and the learning algorithm can find
the representation, this (tautologically) implies that the Transformer
distribution converges to $\hat{M}_{\cdots}$. Similarly if the Transformer is
trained on $x^{j}$ sampled from $M_{s(j),L(j),n}(x)$ for $j=1,2,3,...$, it
converges to $M_{\infty,\infty,n}$. For a Transformer with context length $n$
increasing over time, even $\hat{M}_{\cdots}\to M$ could be possible. To
guarantee normalized probabilities when learning $\widetilde{M}_{\cdots}$ and
$M_{\cdots}^{norm}$, we do _not_ introduce a $\bot$-padding symbol. For
$\widetilde{M}_{\cdots}$ we train on $\widetilde{D}$ which doesn’t require
padding. For training towards $M_{\cdots}^{norm}$, we pad the $x^{j}$ in
$D^{J}$ to length $n$ with arbitrary symbols from $\mathcal{X}$ and train on
that, but we (have to) cut the log-loss short
$-\sum_{t=1}^{\ell(x)}\log(\text{LLM}(x_{t}|x_{<t}))$, i.e. $\ell(x)$ rather
than $n$, so as to make the loss hence gradient hence minimum independent of
the arbitrary padding.

#### Limit-normalized $\widetilde{M}$.

This is the easiest case: $\widetilde{D}$ removes strings shorter than $n$
from $D^{J}$ (sampled from $M$), so $\widetilde{D}$ has distribution
$\widetilde{M}$, hence for $D=\widetilde{D}$, the log-loss is minimized by
$p_{\theta}=\hat{\widetilde{M}}$, i.e. training on $\widetilde{D}$ makes
$p_{\theta}$ converge to $\hat{\widetilde{M}}$ (under the stated assumptions).

#### Unnormalized $M$.

For this case we need to augment the (token) alphabet $\mathcal{X}$ with some
(absorbing) padding symbol $\bot$: Let $D_{\bot}$ be all $x\in D^{J}$ but
padded with some $\bot$ to length $n$. We can extend
$M:\mathcal{X}^{*}\to[0;1]$ to
$M_{\\!\bot\\!}:\mathcal{X}^{*}\cup\\{\bot\\}\to[0;1]$ by

$\displaystyle M_{\\!\bot\\!}(x)\leavevmode\nobreak\ $
$\displaystyle:=\leavevmode\nobreak\ M(x)$ for all $\displaystyle
x\in\mathcal{X}^{*}$ $\displaystyle
M_{\\!\bot\\!}(x\bot^{\\!t})\leavevmode\nobreak\ $
$\displaystyle:=\leavevmode\nobreak\
M(x)-\textstyle\sum_{a\in\mathcal{X}}M(xa)$ for all $\displaystyle
x\in\mathcal{X}^{*}\leavevmode\nobreak\ \leavevmode\nobreak\
\text{and}\leavevmode\nobreak\ \leavevmode\nobreak\ t\geq 1$ $\displaystyle
M_{\\!\bot\\!}(x)\leavevmode\nobreak\ $ $\displaystyle:=\leavevmode\nobreak\
0$ for all $\displaystyle x\not\in\mathcal{X}^{*}\\{\bot\\}^{*}$

It is easy to see that $D_{\bot}$ has distribution $M_{\\!\bot}$, hence for
$D=D_{\bot}$, the log-loss is minimized by $p_{\theta}=\hat{M}_{\\!\bot}$.
Since $\hat{M}_{\\!\bot\\!}(x)$ restricted to $x\in\mathcal{X}^{*}$ is just
$\hat{M}(x)$, training on $D_{\bot}$ makes $p_{\theta}(x)$ converge to
$\hat{M}(x)$ for $x\in\mathcal{X}^{*}$. Though it is possible to train neural
models that would converge in the limit to the standard (computable)
Solomonoff prior, we focus on the normalized version due to Remark 7.
_Training variation:_ Note that for $M$, the Transformer is trained to predict
$x\bot$ if $\ell(x)<n$. If $\ell(x)<n$ is due to the time limit $s$ in
$U^{s}$, it is preferable to _not_ train the Transformer to predict $\bot$
after $x$, since for $s\to\infty$, which we are ultimately interested in, $x$
may be extended with proper symbols from $\mathcal{X}$. One way to achieve
this is to cut the log-loss (only) in this case at $t=\ell(x)$ similar to
$M^{norm}$ below to not reward the Transformer for predicting $\bot$.

###  B.1 Normalized Solomonoff Loss

Here is the derivation of the loss.

$\displaystyle\text{Loss}(\theta)\leavevmode\nobreak\ $
$\displaystyle:=\leavevmode\nobreak\ -\frac{1}{J}\sum_{x\in D^{J}}\log
p_{\theta}(x)\leavevmode\nobreak\ =\leavevmode\nobreak\ -\frac{1}{J}\sum_{x\in
D^{J}}\sum_{t=1}^{\ell(x)}\log p_{\theta}(x_{t}|x_{<t})$
$\displaystyle=\leavevmode\nobreak\ -\frac{1}{J}\sum_{t=1}^{n}\sum_{x\in
D^{J}\wedge\ell(x)\geq t}\log p_{\theta}(x_{t}|x_{<t})\leavevmode\nobreak\
=\leavevmode\nobreak\
-\sum_{t=1}^{n}\sum_{x_{1:t}}\hat{M}_{D^{J}}(x_{1:t})\log
p_{\theta}(x_{t}|x_{<t})$ $\displaystyle=\leavevmode\nobreak\
-\sum_{t=1}^{n}\sum_{x_{<t}}\Big{(}\sum_{x_{t}}\hat{M}_{D^{J}}(x_{1:t})\Big{)}\Big{(}\sum_{x_{t}}\hat{M}^{norm}(x_{t}|x_{<t})\log
p_{\theta}(x_{t}|x_{<t})\Big{)}$

where the last equality follows from (3).

##  Appendix C Generalized Solomonoff Semimeasure

#### Streaming functions.

A streaming function $\varphi$ takes a growing input sequence and produces a
growing output sequence. In general, input and output may grow unboundedly or
stay finite. Formally, $\varphi:\mathcal{X}^{\\#}\to\mathcal{X}^{\\#}$, where
$\mathcal{X}^{\\#}:=\mathcal{X}^{\infty}\cup\mathcal{X}^{*}$. In principle
input and output alphabet could be different, but for simplicity we assume
that all sequences are binary, i.e. $\mathcal{X}=\\{0,1\\}$. For $\varphi$ to
qualify as a streaming function, we need to ensure that extending the input
only extends and does not modify the output. Formally, we say that

$\displaystyle\varphi\leavevmode\nobreak\ \text{is monotone
\leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\
iff}\leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\ [\forall
q\sqsubseteq p:\varphi(q)\sqsubseteq\varphi(p)]$

where $q\sqsubseteq p$ means that $q$ is a prefix of $p$ i.e. $\exists
r\in\mathcal{X}^{\\#}:qr=p$, and $\sqsubset$ denotes strict prefix
$r\neq\epsilon$. $p$ is $\varphi$-minimal for $x$ if $\exists r:\phi(p)=xr$
and $\forall r\forall q\sqsubset p:\phi(q)\neq xr$. We will denote this by
$\varphi(p)=x*$. $p$ is the shortest program outputting a string starting with
$x$.

#### Monotone Turing Machines (MTM).

A Monotone Turing machine $T$ is a Turing machine with left-to-right read-only
input tape, left-to-right write-only output tape, and some bidirectional work
tape. The function $\varphi_{T}$ it computes is defined as follows: At any
point in time after writing the output symbol but before moving the output
head and after moving the input head but before reading the new cell content,
if $p$ is the content left of the current input tape head, and $x$ is the
content of the output tape up to the current output tape head, then
$\varphi_{T}(p):=x$. It is easy to see that $\varphi_{T}$ is monotone. We
abbreviate $T(p)=\varphi_{T}(p)$. There exist (so called optimal) universal
MTM $U$ that can emulate any other MTM via $U(i^{\prime}q)=T_{i}(q)$, where
$T_{1},T_{2},...$ is an effective enumeration of all MTMs and $i^{\prime}$ a
prefix encoding of $i$ (Hutter, 2004; Li et al., 2019).

###  C.1 Proof of Theorem 9

See 9

We can effectively sample from any computable $Q$ if we have access to
infinitely many fair coin flips. The conditions on $Q$ ensure that the entropy
of $Q$ is infinite, and stays infinite even when conditioned on any
$q\in\mathcal{X}^{*}$. This also allows the reverse: Converting a sample from
$Q$ into infinitely many uniform random bits. Forward and backward conversion
can be achieved sample-efficiently via (bijective) arithmetic (de)coding. This
forms the basis of the proof below. The condition of $Q$ being a proper
measure rather than just being a semimeasure is also necessary: For instance,
for $Q(q)=4^{-\ell(q)}$, on a Bernoulli($\frac{1}{2}$) sequence
$x_{1:\infty}$, $M_{U}(x_{t}|x_{<t})\to\frac{1}{2}$ as it should, one can show
that $M_{U}^{Q}(x_{t}|x_{<t})<\frac{1}{3}$ for infinitely many $t$ (w.p.1).

###### Proof.

_(sketch)_ Let $0.q_{1:\infty}\in[0;1]$ be the real number with binary
expansion $q_{1:\infty}$. With this identification, $Q$ can be regarded as a
probability measure over $[0;1]$. Let $F:[0;1]\to[0;1]$ be its cumulative
distribution function, which can explicitly be represented as
$F(0.q_{1:\infty})=\sum_{t:q_{t}=1}Q(\Gamma_{q_{<t}0})$, since
$[0;\,0.q_{1:\infty})={\dot{\smash{\bigcup}}}_{t:q_{t}=1}0.\Gamma_{q_{<t}0}$,
where $0.\Gamma_{q}=[0.q0^{\infty};\,0.q1^{\infty})$ and
$\dot{\smash{\bigcup}}$ denotes disjoint union. Now assumption
$Q(q)>0\leavevmode\nobreak\ \forall q\in\mathcal{X}^{*}$ implies that $F$ is
strictly increasing, and assumption $Q(q_{1:n})\to 0$ implies that $F$ is
continuous. Since $F(0)=0$ and $F(1)=1$, this implies that $F$ is a bijection.
Let $0.p_{1:\infty}=F(0.q_{1:\infty})$ and
$0.q_{1:\infty}=F^{-1}(0.p_{1:\infty})$. 333Note that $p_{1:m}$ is uniformly
distributed and is (for some $m$) essentially the arithmetic encoding of
$q_{1:n}$ with one caveat: The mapping from sequences to reals conflates
$0.q10^{\infty}=0.q01^{\infty}$. Since the set of all conflated sequences has
probability $0$, (under $Q$ as well as Bernoulli($\frac{1}{2}$)), any error
introduced due to this conflation has no effect on the distribution
$M_{U}^{Q}(x)$.. Further for some finite prefix $q\sqsubset q_{1:\infty}$, we
partition the interval

$\displaystyle[0.p_{1:\infty}^{0};\,0.p_{1:\infty}^{1})\leavevmode\nobreak\
:=\leavevmode\nobreak\ [F(0.q0^{\infty});F(0.q1^{\infty}))\leavevmode\nobreak\
=:\leavevmode\nobreak\ \dot{\bigcup}_{p\in\Phi(q)}0.\Gamma_{p}$

into a minimal set of binary intervals $0.\Gamma_{p}$, where $\Phi(q)$ is a
minimal prefix free set in the sense that for any $p$, at most one of $p$,
$p0$, $p1$ is in $\Phi(q)$. An explicit representation is

$\displaystyle\Phi(q)\leavevmode\nobreak\ :=\leavevmode\nobreak\
\\{p_{<t}^{0}1:t>t_{0}\wedge p_{t}^{0}=0\\}\leavevmode\nobreak\
\dot{\cup}\leavevmode\nobreak\ \\{p_{<t}^{1}0:t>t_{0}\wedge p_{t}^{1}=1\\}$

where $t_{0}$ is the first $t$ for which $p_{t}^{0}\neq p_{t}^{1}$. Now we
plug

$\displaystyle Q(q)\leavevmode\nobreak\ $ $\displaystyle=\leavevmode\nobreak\
F(0.q1^{\infty})-F(0.q0^{\infty})\leavevmode\nobreak\ =\leavevmode\nobreak\
\sum_{p\in\Phi(q)}|0.\Gamma_{p}|\leavevmode\nobreak\ =\leavevmode\nobreak\
\sum_{p\in\Phi(q)}2^{-\ell(p)}\leavevmode\nobreak\ \leavevmode\nobreak\
\leavevmode\nobreak\ \text{into}$ $\displaystyle
M_{U}^{Q}(x)\leavevmode\nobreak\ $ $\displaystyle\equiv\leavevmode\nobreak\
\sum_{q:U(q)=x*\\!\\!\\!\\!}Q(q)\leavevmode\nobreak\ =\leavevmode\nobreak\
\sum_{\\!\\!\\!\\!q:U(q)=x*\leavevmode\nobreak\ \leavevmode\nobreak\
}\sum_{p\in\Phi(q)\\!\\!\\!\\!}2^{-\ell(p)}\leavevmode\nobreak\
=\leavevmode\nobreak\
\sum_{p:V(p)=x*\\!\\!\\!\\!}2^{-\ell(p)}\leavevmode\nobreak\
=\leavevmode\nobreak\ M_{V}(x)$

where $V(p):=U(q)$ for the maximal $q$ such that $p\in\Phi(q)$. The maximal
$q$ is unique, since $\Phi(q)\cap\Phi(q^{\prime})=\\{\\}$ if $q\not\sqsubseteq
q^{\prime}$ and $q^{\prime}\not\sqsubseteq q$, and finite since $F$ is
continuous.

It remains to show that $V$ is universal. Let $p^{\imath}$ be such that
$0.\Gamma_{p^{\imath}}\subseteq[F(0.\imath^{\prime}0^{\infty});F(0.\imath^{\prime}1^{\infty}))$.
The choice doesn’t matter as long as it is a computable function of $\imath$,
but shorter is “better”. This choice ensures that
$F^{-1}(0.p^{\imath}*)=0.\imath^{\prime}...$ whatever the continuation $*$ is.
Now let
$F(q_{1:\infty})_{\text{tail}}:=F(q_{1:\infty})_{\ell(p^{\imath})+1:\infty}=p_{\ell(p^{\imath})+1:\infty}$
if $q_{1:\infty}$ starts with $\imath^{\prime}$, and arbitrary, e.g.
$F(q_{1:\infty})$, otherwise. Let $T$ be a MTM with
$T(q_{1:\infty}):=U_{0}(F(q_{1:\infty})_{\text{tail}})$ for some universal MTM
$U_{0}$. By Kleene’s 2nd recursion theorem (Sipser, 2012, Chp.6), there exists
an $i$ such that $T_{i}(q)=T(i^{\prime}q)\leavevmode\nobreak\ \forall q$. Let
$\dot{k}:=\ell(i^{\prime})+1$ and $\dot{\ell}:=\ell(p^{i})+1$ and
$q_{<\dot{k}}:=i^{\prime}$, hence $p_{<\dot{\ell}}=p^{i}$. Now
$V(p_{1:\infty})=U(q_{1:\infty})$ implies

$\displaystyle V(p^{i}p_{\dot{\ell}:\infty})\leavevmode\nobreak\
=\leavevmode\nobreak\ U(i^{\prime}q_{\dot{k}:\infty})\leavevmode\nobreak\
=\leavevmode\nobreak\ T_{i}(q_{\dot{k}:\infty})\leavevmode\nobreak\
=\leavevmode\nobreak\ T(i^{\prime}q_{\dot{k}:\infty})\leavevmode\nobreak\
=\leavevmode\nobreak\
U_{0}(F(i^{\prime}q_{\dot{k}:\infty})_{\text{tail}})\leavevmode\nobreak\
=\leavevmode\nobreak\ U_{0}(p_{\dot{\ell}:\infty})$

hence $V$ is universal, which concludes the proof. ∎

#### Practical universal streaming functions.

Turing machines are impractical and writing a program for a universal
streaming function is another layer of indirection which is best to avoid.
Programming languages are already universal machines. We can define a
conversion of real programs from/to binary strings and prepend it to the input
stream. When sampling input streams $q_{1:\infty}$ we convert the beginning
into a program of the desired programming language, and feed it the tail as
input stream.

##  Appendix D Experiment methodology details

###  D.1 Architecture details

Table 1: Architectures  RNN and LSTMs | S | M | L
---|---|---|---
RNN Hidden size | 16 | 32 | 128
Number of RNN layers | 1 | 2 | 3
MLP before RNN layers | (16,) | (32, 32) | (128, 128, 128)
MLP after RNN layers | (16,) | (32, 32) | (128, 128, 128)
Transformer SINCOS |  |  |
Embedding dimension | 16 | 64 | 256
Number of heads | 2 | 4 | 4
Number of layers | 2 | 4 | 6

#### RNN.

A vanilla multi-layer RNN (Elman, 1990) with hidden sizes and multi-layer
perceptron (MLP) before and after the RNN layers as described in Table 1.

#### Stack-RNN.

A multi-layer RNN controller with hidden sizes and MLP exactly the same as the
RNN and LSTMs on Table 1 with access to a differentiable stack (Joulin and
Mikolov, 2015). The controller can perform any linear combination of push,
pop, and no-op on the stack of size according to Table 1, with action weights
given by a softmax over a linear readout of the RNN output. Each cell of the
stack contains a real vector of dimension 6 and the stack size is 64 for all
(S, M and L) sizes.

#### Tape-RNN.

A multi-layer RNN controller with hidden sizes according to the Table 1 with
access to a differentiable tape, inspired by the Baby-NTM architecture (Suzgun
et al., 2019). The controller can perform any linear combination of write-
right, write-left, write-stay, jump-left, and jump-right on the tape, with
action weights given by a softmax. The actions correspond to: writing at the
current position and moving to the right (write-right), writing at the current
position and moving to the left (write-left), writing at the current position
(write-stay), jumping $\ell$ steps to the right without writing (jump-right),
where $\ell$ is the length of the input, and jumping $\ell$ steps to the left
without writing (jump-left). As in the Stack-RNN, each cell of the tape
contains a real vector of dimension 6 and the tape size is 64 for all (S, M
and L) sizes.

#### LSTM.

A multi-layer LSTM (Hochreiter and Schmidhuber, 1997) of hidden sizes
according to Table 1.

#### Transformer decoder.

A vanilla Transformer decoder (Vaswani et al., 2017). See Table 1 for the
embedding dimension, number of heads and number of layers for each model size
(S, M and L). Each layer is composed of an attention layer, two dense layers,
and a layer normalization. We add a residual connections as in the original
architecture (Vaswani et al., 2017). We consider the standard sin/cos (Vaswani
et al., 2017) positional encoding.

###  D.2 CTW

Below is an ultra-compact introduction to (sampling from) CTW (Willems et al.,
1995, 1997). For more explanations, details, discussion, and derivations, see
(Catt et al., 2024, Chp.4).

#### A variable-order Markov process.

is a probability distribution over (binary) sequences $x_{1},x_{2},x_{3},...$
with the following property: Let $S\subset\\{0,1\\}^{*}$ be a complete suffix-
free set of strings (a reversed prefix-free code) which can equivalently be
viewed as a perfect binary tree. Then
$p(x_{t}=0|x_{<t};S,\Theta_{S}):=\theta_{s}$ if (the unique) context of
$x_{t}$ is $s=x_{t-\ell(s):t-1}\in S$, and
$\Theta_{S}:=(\theta_{s}\in[0;1]:s\in S)$. We arbitrarily define $x_{t}=0$ for
$t\leq 0$.

#### Intuition about Variable-order Markov sources

VOMS considers data generated from tree structures. For example, given the
binary tree

                    Root
                 0/      \1
            Leaf_0        Node
                        0/     \1
                  Leaf_10       Leaf_11

and given the history of data “011“ (where 0 is the first observed datum and 1
is the last one) the next sample uses $\text{Leaf}_{11}$ (because the last two
data points in history were 11) to draw the next datum using a sample from a
Beta distribution with parameter $\text{Leaf}_{11}$. Say we sample a 0, thus
history is then transformed into “0110” and $\text{Leaf}_{10}$ will be used to
sample the next datum (because now the last two datapoints that conform to a
leaf are "10"), and so forth. This way of generating data is very general and
can produce many interesting patterns ranging from simple regular patterns
like $01010101$ or more complex ones that can have stochastic samples in it.
Larger trees can encode very complex patterns indeed.

#### Sampling from CTW.

Context Tree Weighting (CTW) is a Bayesian mixture over all variable-order
Markov sources of maximal order $D\in\mathbb{N}_{0}$, i.e. over all trees $S$
of maximal depth $D$ and all $\theta_{s}\in[0;1]$ for all $s\in S$. The CTW
distribution is obtained as follows: We start with an empty (unfrozen)
$S=\\{\epsilon\\}$. Recursively, for each unfrozen $s\in S$ with $\ell(s)<D$,
with probability ${{}^{1}\\!/\\!_{2}}$ we freeze $s$; with probability
${{}^{1}\\!/\\!_{2}}$ we split $S\leftarrow S\setminus\\{s\\}\cup\\{0s,1s\\}$
until all $s\in S$ are frozen or $\ell(s)=D$. Then we sample $\theta_{s}$ from
$\text{Beta}({{}^{1}\\!/\\!_{2}},{{}^{1}\\!/\\!_{2}})$ for all $s\in S$.
Finally for $t=1,2,3,...$ we sample $x_{t}$ from
$p(x_{t}|x_{<t};S,\Theta_{S})$.

#### Computing CTW.

The CTW probability $P_{\text{CTW}}(x_{1:n})$ can be calculated as follows:
Let $a_{s}:=|\\{t\in\\{1,...,n\\}:x_{t}=0\wedge x_{t-\ell(s):t-1}=s\\}|$ count
the number of $x_{t}=0$ immediately preceded by context $s\in\\{0,1\\}^{*}$,
and similarly $b_{s}:=|\\{t:x_{t}=1\wedge x_{t-\ell(s):t-1}=s\\}|$. Let
$x_{1:n}^{s}\in\\{0,1\\}^{a_{s}+b_{s}}$ be the subsequence of $x_{t}$’s that
have context $s$. For given $\theta_{s}$ for $s\in S$, $x_{1:n}^{s}$ is i.i.d.
(Bernoulli($1-\theta_{s}$)). Hence for
$\theta_{s}\sim\text{Beta}({{}^{1}\\!/\\!_{2}},{{}^{1}\\!/\\!_{2}})$,
$P(x_{1:n}^{s}|s\in
S)=P_{\text{KT}}(a_{s},b_{s}):=\int_{0}^{1}\theta_{s}^{a_{s}}(1-\theta_{s})^{b_{s}}\text{Beta}({{}^{1}\\!/\\!_{2}},{{}^{1}\\!/\\!_{2}})(\theta_{s})d\theta_{s}$.
If $s\not\in S$, we split $x_{1:n}^{s}$ into $x_{1:n}^{0s}$ and
$x_{1:n}^{1s}$. By construction of $S$, a tentative $s\in S$ gets replaced by
$0s$ and $1s$ with 50% probability, recursively, hence
$P_{\text{CTW}}(x_{1:n}^{s})=\frac{1}{2}P_{\text{KT}}(a_{s},b_{s})+\frac{1}{2}P_{\text{CTW}}(x_{1:n}^{0s})P_{\text{CTW}}(x_{1:n}^{1s})$
terminating with $P_{\text{CTW}}(x_{1:n}^{s})=P_{\text{KT}}(a_{s},b_{s})$ when
$\ell(s)=D$. This completes the definition of $P_{\text{CTW}}(x_{1:n})\equiv
P_{\text{CTW}}(x_{1:n}^{\epsilon})$. Efficient $O(nD)$ algorithms for
computing $P_{\text{CTW}}(x_{1:n})$ (and updating $n\to n+1$ in time $O(D)$)
and non-recursive definitions can be found in Catt et al. (2024, Chp.4).

#### Distributions of Trees.

A tree has depth $\leq d$ if either it is the empty tree or if both its
subtrees have depth $<d$. Therefore the probability of sampling a tree of
depth $\leq d$ is $F(d)=\frac{1}{2}+\frac{1}{2}F(d-1)^{2}$, with
$F(0)=\frac{1}{2}$. Therefore the probability of sampling a tree of depth $d$
is $P(d)=F(d)-F(d-1)$ for $d<D$ and $P(D)=1-F(D-1)$. The theoretical curve
($P(0)=\frac{1}{2}$, $P(1)=\frac{1}{8}$, $P(2)=\frac{9}{128}$,…) is plotted in
Fig. 7(a) together with the empirical distribution. More meaningful is
probably the expected number of leaf nodes at each level $d$. Since each node
at level $d$ is replaced with prob. $\frac{1}{2}$ by two nodes at level $d+1$,
the expected number of leaf nodes $E(d)$ is the same at all levels $d<D$.
Since $E(0)=\frac{1}{2}$, we have $E(d)=\frac{1}{2}$ for all $d<D$ and
$E(D)=1$, hence the total expected number of leaf nodes is
$E_{+}=\frac{1}{2}D+1$. While this doesn’t sound much, it ensures that for
$N=10^{\prime}000$ samples, we uniformly test $5^{\prime}000$ contexts for
each length $d<D$. We can get some control over the distribution of trees by
splitting nodes at level $d$ with probability $\alpha_{d}\in[0;1]$ instead of
$\frac{1}{2}$. In this case, $E(d)=2\alpha_{0}\cdot...\cdot
2\alpha_{d-1}(1-\alpha_{d})$ for $d<D$. So for $\alpha_{d}>\frac{1}{2}$ we can
create trees of size exponential in $D$, and (within limits) any desired depth
distribution.

###  D.3 Chomsky

Table 2:  Table taken from (Deletang et al., 2022). Tasks with their level in
the Chomsky hierarchy and example input/output pairs. The $\dagger$ denotes
permutation-invariant tasks; the $\star$ denotes counting tasks; the $\circ$
denotes tasks that require a nondeterministic controller; and the $\times$
denotes tasks that require superlinear running time in terms of the input
length.

Level | Name | Example Input | Example Output
---|---|---|---
Regular (R) | Even Pairs | $aabba$ | True
Modular Arithmetic (Simple) | $1+2-4$ | $4$
Parity Check† | $aaabba$ | True
Cycle Navigation† | $011210$ | $2$
Deterministic context-free (DCF) | Stack Manipulation |  $abbaa$ pop push $a$ pop | $abba$
Reverse String | $aabba$ | $abbaa$
Modular Arithmetic | $-(1-2)\cdot(4-3\cdot(-2))$ | $0$
Solve Equation∘ | $-(x-2)\cdot(4-3\cdot(-2))$ | $1$
Context-sensitive (CS) | Duplicate String | $abaab$ | $abaababaab$
Missing Duplicate | $10011021$ | $0$
Odds First | $aaabaa$ | $aaaaba$
Binary Addition | $10010+101$ | $10111$
Binary Multiplication× | $10010*101$ | $1001000$
Compute Sqrt | $100010$ | $110$
Bucket Sort†★ | $421302214$ | $011222344$

##  Appendix E UTMs: Brainf*ck and BrainPhoque

Our BrainPhoque (BP) UTM produces program evaluation traces that are
equivalent to those of brainf*ck (BF) programs (Müller, 1993) (see also
$\mathcal{P}^{\prime\prime}$ (Böhm, 1964)), but the programs are written
slightly differently: they are even less human-readable but have better
properties when sampling programs.

We start by giving a quick overview of the BF machine, then explain why we
need a slightly different machine, and its construction. Finally we explain
how to shorten sampled programs and calculate an upper bound on the log-loss.

See Figure 6 for some sample programs and outputs.

###  E.1 Brainf*ck

BF is one of the smallest and simplest Turing-complete programming languages.
It features a read-only input tape, a working tape, and a write-only output
tape. These tapes are assumed infinite but for practical purposes they are
usually fixed at a finite and constant length and initialized with 0.444The
tape could also grow on request, but this tends to slow down program
evaluation. Each tape cell can contain a non-negative integer, which can grow
as large as the ’alphabet size’. Above that number, it loops back to 0. In the
paper, we choose an alphabet size of 17.

Each tape has a pointer. For simplicity, the pointer of the working tape is
called WTP, and the value at the WTP is called _datum_ , which is an integer.

BF uses 8 instructions <>+-[],. which are:

  * •

< and > decrement and increment the WTP, modulo the length of the tape.

  * •

+ and - increment and decrement the datum, modulo the alphabet size.

  * •

[ is a conditional jump: if the datum is 0, the instruction pointer jumps to
the corresponding (matching) ].

  * •

] is an unconditional jump to the corresponding [.555For efficiency reasons
the instruction ] is usually defined to jump to the matching [ if the datum is
non-zero. We stick to a unconditional jump for simplicity reasons.

  * •

, copies the number under the reading tape pointer into the datum cell, and
increments the reading pointer.

  * •

. copies the datum to the output tape at the output pointer and increments the
output pointer.

In this paper we do not use an input tape, so we do not use the , instruction.

When evaluating a program, the instruction pointer is initially on the first
instruction, the output tape is empty, and the working tape is filled with
zeros. Then the instruction under the instruction pointer is evaluated
according to the above rules, and the instruction pointer is moved to the
right. Evaluation terminates when the number of evaluated instructions reaches
a given limit, or when the number of output symbols reaches a given limit.

For a sequence of instructions A[B]C, where A, B and C are sequences of (well-
balanced) instructions, we call B the _body_ of the block and C the
_continuation_ of the block.

###  E.2 BrainPhoque: Simultaneous generation and evaluation

We want to sample arbitrary BF programs and evaluate them for $T$ steps each.
To maximize computation efficiency of the sampling and running process,
programs containing unbalanced parentheses are made valid, in particular by
skipping any additional ].

Since we want to approximate _normalized_ Solomonoff induction 3, we can make
a few simplifications. In particular, programs do not need to halt explicitly,
which removes the need for a halting symbol and behaviour.666The halting
behaviour can be recovered by ending programs with a particular infinite loop
such as []+[] (which loops whether the datum is zero or not), and terminate
the evaluation (instead of looping forever) upon evaluating this sequence.
Hence we consider that _all_ programs are infinite, but that at most $T$
instructions are evaluated. The difficulty with BF programs is that the
evaluated instructions can be at arbitrary locations on the program tape,
since large blocks [...] may be entirely skipped, complicating both the
sampling process and

This can be fixed by generating BF programs as trees, where branching on
opening brackets [: The left branch corresponds to the body of the block (and
terminates with a ]), while the right branch corresponds to the continuation
of the block. When encountering an opening bracket for the first time during
evaluation, which branch is evaluated next depends on the datum. Hence, to
avoid generating both branches, we need to generate the program _as it is
being evaluated_ : when sampling and evaluating a [, if the datum is 0 we
follow the right branch and start sampling the continuation without having to
sample the body (for now); conversely, if the datum is not zero, we follow the
left branch and start sampling and evaluating the continuation. If the same
opening bracket is later evaluated again with a different datum value, the
other branch may be generated and evaluated.

Our implementation of program generation and evaluation in BrainPhoque uses
one growing array for the program, one jump table, and one stack for yet-
unmatched open brackets.

If the instruction pointer is at the end of the program, a new instruction
among +-<>[]. is sampled; if it is [ and the datum is 0, it is changed to {.
The new instruction is appended to the program, and is then evaluated. If the
new instruction is [, the next instruction to be sample (and appended to the
program) is the beginning of the body of the block, but if instead the new
instruction is {, the next instruction to be sampled (and appended to the
program) is the continuation of the body. At this point the jump table does
not yet need to be updated — since the next instruction to evaluate is also
the next instruction in location. The jump table is updated to keep track of
where the continuations and bodies are located in the program. If the
instruction pointer eventually comes back for a second time of an opening
bracket [ (resp. {) and the datum is now 0 (resp. not 0), the continuation
(resp. body) of the block must now be sampled and appended to the program; and
now the jump table must be updated accordingly.

The stack of unmatched brackets is updated only when the body of a block is
being generated.

Some properties of BrainPhoque:

  * •

If a program is run for $t+k$ steps, it behaves the same on the first $t$
steps for all values of $k$.777While this is an obviously desirable property,
it is also easy to overlook. In particular, unmatched opening brackets behave
the same whether they will be matched or not.

  * •

Program generation (sampling) only requires a single growing-only array. A
tree structure is not required. This is the reason for having the additional {
instruction, which makes it clear — once evaluated the second time — whether
the body or the continuation has already been generated.

  * •

If the instruction pointer is at cell $n$, then all instructions to the left
of $n$ have been evaluated at least once. If this is the first evaluation of
cell $n$, then no instruction to the right of $n$ have been evaluated yet.

Figure 6: Some BrainPhoque programs and their corresponding outputs (truncated
at 256 symbols). The smallest bars (in red) correspond to the value 0, and the
largest bars (in gray) correspond to value 16. The programs have been reduced
after evaluation by removing a set of unnecessary instructions. Most of the
generated outputs are regular, and only about 1 in $5000$ sampled programs
exhibits non-regular patterns. But see Table 3 for a way to improve these
numbers and generate more interesting and complex sequences.

Table 3:  Pre-trained BP program sampling probabilities Instead of sampling
programs uniformly, we can sample them w.r.t. any probability distribution $Q$
that satisfies Theorem 9. We initially sampled programs uniformly and filtered
out ‘boring’ sequences. Then we trained $Q$ via cross-entropy to mimic the
distribution of ‘interesting’ sequences. We used a 2nd-order Markov process as
a model for $Q$. While uniform sampling resulted in only 0.02% interesting
sequences, sampling from $Q$ increased it to 2.5%, a 137-fold improvement. The
table on the left shows the 0th, 1st, and 2nd order Markov processes
$Q(p_{t})$, $Q(p_{t}|p_{t-1})$, and $Q(p_{t}|p_{t-2}p_{t-1})$ from which BP
programs are sampled, for $p_{\cdot}\in\\{\texttt{<>+-[]\\{.}\\}$, but where
results for [ and { have been merged. Each row corresponds to a context (none
or $p_{t-1}$ or $p_{t-2}p_{t-1}$). We also included
$Q(p_{1}|p_{0}\\!\\!:=\\!\\!\texttt{\\_})$ and
$Q(p_{1}|p_{-1}p_{0}\\!\\!:=\\!\\!\texttt{\\_\\_})$. The entries in each
column correspond to the sampling probability of $p_{t}$ in the corresponding
row-context. Training on interesting sequences has led to a non-uniform
distribution $Q$. Universality is preserved for any $k$-order Markov process,
provided all transition probabilities are non-zero. The probability
$Q(\texttt{.})$ of outputting a symbol has nearly doubled from 0.14 to 0.27 on
average, while the probability of loop brackets ([,]) reduced to 0.07 each on
average. The marginal probabilities $Q(\texttt{<})\approx Q(\texttt{>})\approx
Q(\texttt{+})\approx Q(\texttt{-})\approx 1/7$ have not changed much, but many
of the conditional ones have. Certain combination of instructions are now
blocked: For instance +- and -+ and <> and >< have probability close to $0$,
since they cancel each other and hence are redundant. Some triples such as ][-
and <+ and >- and others are enhanced.
Caveat: We did not have time to retrain our NN models on these newly generated
sequences (experiments are still running). But since the statistics is
improved, we expect the results in Figures 4 and 5 to improve or at least not
deteriorate.

###  E.3 Solomonoff log-loss upper bound and shortening programs

We tried to provide a meaningful upper bound for the loss of Solomonoff
induction for Figure 4, but this is far from easy. See Section 3 for context.
As mentioned there, to calculate a more meaningful upper bound, we shorten
programs by recursively removing unnecessary open brackets and closing
brackets that are unmatched, as well as all self-cancelling pairs of
instructions (+-, -+, <>,><). Moreover, we remove all instructions of the
program that have been evaluated for the first time after the last evaluation
of a print . instruction (since they do not participate in producing the
output. This procedure often reduces programs by a third. Programs that do not
output anything are thus reduced to the empty program (probability 1).

If $q$ is a sampled program, then $\tilde{q}$ is the corresponding shortened
program. We calculate an upper bound on the loss of the Solomonoff predictor,
with U = BrainPhoque, on a set of sampled programs
$\hat{Q}=(q^{1},\dots,q^{J})$ and corresponding outputs
$(U(q^{1})_{1:256},\dots,U(q^{J})_{1:256})$,

$\displaystyle\text{Loss}(M_{U},\hat{Q})=\sum_{q\in\hat{Q}}-\log\sum_{p:U(p)_{1:256}=U(q)_{1:256}}7^{-\ell(p)}\leq\sum_{q\in\hat{Q}}-\log
7^{-\ell(\tilde{q})}=\log(7)\sum_{q\in\hat{Q}}\ell(\tilde{q})$ (4)

since the program alphabet is not binary but has $7$ instructions.
Unfortunately, even after reduction this bound is still quite loose, but
improving this bound meaningfully would likely require a much larger amount of
computation.

##  Appendix F Additional Results Details

Below we show additional results of the experiments on the VOMS (Figure 7),
the Chomsky tasks (Figure 8) and UTM source (Figures 9 and 10). Finally, on
Figure 11 we show further details of the length generalization analysis.

(a) Tree depth per trajectory.

(b) Context length per datapoint.

(c) Average cumulative regret per tree depth of the generator.

(d) Average Instantaneous regret per current context length (only context-
lengths up to $11$).

(e) Average Instantaneous regret per current context length (all context-
lenghts).

Figure 7: Detailed results for the same $6$k sequences as in Figure 2. Top two
panels show histograms over tree depth (for all trajectories) and current
context length (over all datapoints of all trajectories) use for evaluation in
Figure 2. As expected, most generated trees have low depth and most datapoints
have short contexts. The three lower panels show average cumulative regret per
tree depth, and average instantaneous regret per context length respectively.
Thin lines correspond to individual models (with different random
initialization), bold lines show the median per model size. Across
architectures smaller models only predict well for very short tree depth or
very short context lengths (the maximum context length is upper bounded by the
tree depth, but many contexts are much shorter than the maximum tree depth).
Context lenghts $\geq 11$ are rare, which makes quantitative results in this
regime less reliable.

(a) Mean accuracy per Chomsky task, grouped by model size.

(b) Mean cumulative regret per Chomsky task, grouped by model size.

Figure 8: Detailed performance of networks trained and evaluated on the
Chomsky tasks ($6$k sequences, $400$ sequences per task; main results shown in
Figure 3). Thin lines correspond to a single random initialization of a model,
bolt lines show the median respectively.

(a) Average cumulative regret per program length.

(b) Average accuracy per program length.

(c) Histogram over program lengths.

Figure 9: Results per program length for UTM in-distribution evaluation (same
data as in Figure 4; $6$k sequences, length $256$).

Figure 10: UTM transfer to Chomsky tasks.

(a) Variable-order Markov source (CTW) data.

(b) Chomsky tasks.

(c) UTM data.

Figure 11: Full details of sequence-length generalization results. Models were
trained on sequences of length $256$ on their respective tasks, and are
evaluated on $6$k sequences of length $1024$ from the same data generator
type. Thin lines show individual models, bold lines are the median across
random initializations of the same model. As expected, all models perform
fairly well up to their trained sequence length, and then performance
deteriorates more or less sharply. Most notably, prediction performance of the
transformer models, regardless of their size, degrades very rapidly after step
$256$ and is often an order of magnitude worse than the other models. Across
all experiments, LSTMs perform best in terms of generalizing to longer
sequences.