I like to think of this as the "ultimate JIT compiler": when we start executing a program, we run an optimiser in parallel. Hence the longer the program takes,

I like to think of this as the "ultimate JIT compiler": when we start executing a program, we run an optimiser in parallel. Hence the longer the program takes, the longer we spend optimising it; this focuses our optimisation efforts, similar to how JITs only kick in after functions have been called a certain number of times. The main difference between Hutter's algorithm and a JIT compiler is that JITs operate locally on small pieces of a program, like functions; whilst Hutter's optimisation is global. This causes an interesting problem: how do we switch to the optimised version? JITs don't bother switching calls which are already running; they just send any future calls to the optimised version. Whole-program optimisers can't do that, since there's nothing left to execute once the whole-program has finished. Exponential-restarting is an interesting hack to avoid this, but seems like a last-resort compared to local improvements. I think it would be an interesting project to build an interpreter which works like Hutter Search, but allowing local improvements more like a normal JIT as well. It could keep track of a fixed number of search states (based on some longest-running/recently-used heuristic) to avoid having to always restart from scratch. My guess is it would be pretty slow for "straightforward" tasks (assuming we don't bother to do much "manual" optimisation); long-running tasks with lots of iteration would see gradual speedups (as simple optimisations are found for their hottest loops); whilst a few very hard tasks, left running for a long time, may finish unexpectedly (when the optimiser stumbles across a much faster approach).