The Solution is the milestone but how to implement it?

There are a lot of problems in the implementation, as first the step 1 ( compute the Kolmogorov complexity) is uncomputable and the step 2 (fit space time complexity resource ) is again uncomputable . But the uncomputability limit is not the worst . The big problem is the computational complexity to execute these steps. There is not know way to execute these steps without using an absolutely infeasible amount of resources.

As example the solution of step 1 is given by the *Inverse Levin Search* and its optimizations, the steps required to solve this problem are about 2^n so what is possible to do is approximations. Apart this theoretical digression the state of the art is very low and to understand this I made a simple test .

I took a piece of evolution of cellular automata rule 30 and then I tried to compress the result with the top existing compressor . No one is able to compress a bit of this data! The Kolmogorov complexity is one of most short existing ( 1 byte plus log(EvolutionSteps) and there is no reason to think it is greater ) and there are not compressors able to understand it. This experiment is interesting becouse the rule 30 is a special program that generate data statistically random but by definition its Kolmogorov complexity is incredible small so my test show the existing gap inferring a problem that is statistical difficult but easy by its Kolmogorov complexity .

The second step is what a programmer do every day by hand and here this is done in automatic so it is clear (by the existence of programmers ) that we have no tools to solve efficiently this step and there are programs for which it is uncomputable to find the corresponding one with a fixed space-time complexity but there is also another problem very often simply a program fitting space-time restriction does not exist, and is possible only to approximate its behaviour.

Given all this trouble what is possible to do? A simple implementation can be to search a program corresponding to your problem and if you find it probably you can use as a good solution (in some papers there are proof asserting that smaller program is also a fast program ).

However all existing approach can give good solutions only in statistically-not-random problems .

My objective is to give solutions in real simply problems where simple is correctly defined by the Kolmogorov complexity.

### Like this:

Like Loading...

*Related*

Pingback: The Inverse Levin Search « Breakingkeyboards’s Blog