[psandersen]

Interesting idea! I'm not an expert, but if I'm reading you right and the decompressor is Turing complete; you're searching for the smallest Turing machine capable of generating the input sequence?

That would indeed be an optimal compressor and start to enable things like Solomonof induction and AIXI.

Seems the challenge is to get feedback to guide the search for the right Turing machine. With infinite compute can just run an ever expanding set of Turing machines until you get one that generates the input, but without some breakthrough that would enable something like stochastic gradient descent to efficiently work on non-differentiable programs I don't see how it can be made practical.

Perhaps there is some sweet spot thats more general than current compressors that looks at a restrict class of Turing machines that could be feasible.