Marcus Hutter

So I mean, in principle, what you can do is you take any data set, you take these fractals or you take whatever your data set, whatever you have, say a picture of Conway's Game of Life, and you run through all programs.

You take a program of size one, two, three, four, and all these programs, run them all in parallel in so-called dovetailing fashion, give them computational resources, first one 50%, second one half resources, and so on, and let them run.

wait until they hold, give an output, compare it to your data.

And if some of these programs produce the correct data, then you stop and then you have already some program.

It may be a long program because it's faster.

And then you continue and you get shorter and shorter programs until you eventually find the shortest program.

The interesting thing, you can never know whether it's the shortest program because there could be an even shorter program, which is just even slower

You just have to wait here.

But asymptotically, and actually after finite time, you have the shortest program.

So this is a theoretical but completely impractical way of finding the underlying structure in every data set.

And that is what Solomorov induction does and Kolmogorov complexity.

In practice, of course, we have to approach the problem more intelligently.

And then...

if you take resource limitations into account, there's, for instance, the field of pseudo random numbers.

And these are random numbers.

So these are deterministic sequences, but no algorithm, which is fast, fast means runs in polynomial time, can detect that it's actually deterministic.

So we can produce interesting, I mean, random numbers, maybe not that interesting, but just an example.

We can produce complex looking data

And we can then prove that no fast algorithm can detect the underlying pattern.

Yes, it definitely is for artificial intelligence.