Implementing the Solution – 1

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 optimization, the steps required to solve this problem are about 2^n so what is possible to do is approximation. 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 because 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 the space-time restriction does not exist, and it is possible only to approximate its behavior.

Given all these troubles 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 it 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.

Advertisements

One thought on “Implementing the Solution – 1

  1. Pingback: The Inverse Levin Search « Breakingkeyboards’s Blog

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s