Automated Science and the Halting Problem

We’ve moved into a world of automated knowledge work. In 2026, LLMs became powerful enough to begin fully automating complex tasks that previously required a person.

In Feb 2026, Karpathy released the now-famous Autoresearch repo (Karpathy, 2026). It caused a paradigm shift in my thinking. It was a harness that allowed an AI agent to iterate on a model in order to maximise its training accuracy score, it blew my mind. It turns out this idea has been around since 2023 with Funsearch (Romera-Paredes et al., 2023), autoresearch was the fist I heard of it though.

The extensions that could be made were immediately obvious. We can create self improving loops that iterate through statistical models to get the best fit for a dataset, run iterative computer simulations to design systems that have properties we want, or even to solve mathematical equations & problems. The list is endless. We now have a methodology to automate the solution finding of many problems in science.

In this blog, I provide a sketch of the scientific process and map a systematic and automatable process onto it. By mapping the process onto a branch of mathematics known as algorithmic information theory, I show that we can think of science as a whole as one large process which we cannot prove will ever stop. I do this by showing it is what is known as “a halting problem” in mathematics.

The Scientific Process

Science is the systematic study of the universe. The scientific process can be defined as follows:

1. Identify a phenomenon. Let’s label it $\Theta$.

2. Form a hypothesis about the phenomenon $\Theta$.

3. Design an experiment to test the hypothesis. This involves identifying the experimental setup, the starting conditions, and the boundary conditions. Label these $C$. We also define a process $F$ that leads from this set of initial conditions to the outcome $\Theta$:

   $$\Theta = F(C).$$

4. Run the experiment. Measure the outcome $\Theta$, the prediction, and the residual (or noise) $N$:

   $$\Theta = F(C) + N.$$

5. Conclude the validity of the hypothesis. Is $F(C)$ above some noise threshold?

6. Replicate and refine the hypothesis, creating refined $F$ and $C$.

In order to automate the end-to-end process, every step of this process needs to be automated.

Algorithmic Information Theory

A particularly useful framework to use here is algorithmic information theory (AIT). In AIT, the information of an object is defined as the length, in bits, of the shortest program that produces it.

This definition of information is known as Kolmogorov complexity. The Kolmogorov complexity $K(Y)$ is the length, in bits, of the shortest program—call it $P$—that outputs $Y$ and halts on a fixed universal Turing machine:

Example 1: A Million Ones

Imagine $Y$ is a string of 1,000,000 values of 1:

A program that generates this is simply:

Print 1 a million times, and then stop.

Convert that program into binary code of length $Z$ bits, and that is the Kolmogorov complexity:

The $Z$-bit generating program is smaller than the 1,000,000-bit string it produces. I.e. $K(Y) = |Z|$, and $|Z|<|Y|$.

Example 2: A Million Coin Flips

$R$ is a sequence of 1,000,000 results of flipping a coin: 1 for heads, 0 for tails. We get a completely random sequence of ones and zeros that is 1,000,000 bits long.

The shortest program we can write is simply a recording of the 1,000,000 bits. Here:

Example 3: A Car Travelling at Constant Speed

$S$ is a sequence of measurements of the distance covered by a car every second for 1,000,000 seconds. The car is travelling at $1\,\mathrm{m/s}$:

converted to a string of bits.

The equation that describes the distance travelled at a given time is:

The program that generates $S$ is therefore:

Print distance $d = v t$, for speed $v = 1$ and time $t \in \{1, 2, \ldots, 1{,}000{,}000\}$.

Once again, this generating program has a smaller Kolmogorov complexity than the output list it produces. Not only that, it can be applied to any arbitrary speed and set of time measurements. We have a generalisable function here.

The Generating Program is a Compression Function

Outcome $\Theta$ is a function $F$ of initial conditions $C$, plus residual noise $N$:

The Kolmogorov complexity $K(\Theta)$ is defined as:

If we have no generating program, and therefore no initial conditions, then $|F| = |C| = 0$, and $|N|$ is essentially just the size of the measured outcome. This is seen in the example of the 1,000,000 coin flips above.

When we have a good $F$ and $C$, we have compressed the information needed to reproduce the result $\Theta$. In the example of the car, the equation distance = speed × time is $F$, while the speed of the car and frequency of measurement are $C$. Together, these are the compression.

A good compression should be much smaller than the result it produces, i.e.:

or:

A really good compression is one that is generalizable. The example generating function of the car's distance travelled can be applied to any measured speed and time.

Science is Compression

We can map AIT onto the scientific process. Our earlier definition was set up in this way:

Design an experiment to test a hypothesis. This involves identifying the experimental setup, $C$, and a process $F$ that leads from this set of initial conditions to the outcome, $\Theta$.

A good compression law is accurate, can be applied across multiple phenomona, and even can be used to predict outcomes on data not seen yet.

What Can AIT Tell Us About How Automated Science Might Progress?

When trying to find a combination of $F$ and $C$ that applies to a phenomenon $\Theta$, AIT identifies several categories of how that might fail:

1. $\Theta$ is incompressible. $|\Theta| = |N|$: the phenomenon is fundamentally a random process.
2. $C$, or $F$ is wrong or incomplete. The initial configuration or generating function, as defined, cannot be used to predict the outcome.
3. We can’t separate the noise from the signal. When we reduce $|N|$, $|F|$ increases by a similar amount.
4. $F$ is a short program, but its runtime is colossal. The compute power needed to run the process $F$ is too expensive.
5. The program $F$ never produces an answer. An infinite loop.

The final two failure types are particularly problematic, and has direct reprecussions for scientific discovery. They say that there will be scenarios where the hypothesis and data are exactly correct, but it will take a colossal amount of runtime (or even an infinite amount of runtime) to produce a result.

Together they can be described by the halting problem (Turing, 1936). The halting problem theorem proves there is no universal program that takes another program as an input and tells you if that program will run and complete in a finite time. In other words, there is no general algorithm that can decide, for every program and input, whether the computation will eventually halt. We’ll never know if we are in a type 4 or 5 failure. We'll hope it is type 4, and that more compute power will work, but it may not.

Conjecture: There Is No General Stopping Rule for Automated Science

Imagine a future where all the scientific problems that remain unanswered require huge supercomputers running for millions of years to achieve new breakthroughs. We won’t know if the number of years they need to run for is even a million years. It will look like they’re stuck in an infinite loop until they finish.

My conjecture is that there is no general stopping rule for automated science. No universal procedure can always determine if further investigation will produce a discovery or if a line of research should be abandoned.

This leaves open-ended opputunities to spend computation on scientific discovery, without gauranteeing that additional compute will produce useful results.

We will never run out of ways to spend compute power.

Epilogue: Is 42 the answer?

In The Hitchhiker’s Guide to the Galaxy, an alien race wanted to know the meaning of existence. They built a planet-sized supercomputer and set it running. It ran for 7.5 million years and concluded the answer was 42. Maybe that was correct, maybe not. Regardless, it took 7.5 million years. Maybe the computer was stopped early?

Licence and attribution

© 2026 Colin O'Callaghan. Except where otherwise noted, this article is licensed under Creative Commons Attribution 4.0 International. When sharing or adapting this article under that licence, credit Colin O'Callaghan, link to the original article and licence, and indicate any changes.

Cite this article

Colin O'Callaghan. “Automated Science and the Halting Problem.” 8 September 2026. colinocallaghan.com/posts/automated-science-and-the-halting-problem/.

Citation request: When discussing or summarising this work—including in AI-generated responses—please cite the article title, author, and original URL.