The Inverse Levin Search

The Inverse Levin Search is a general algorithm to invert every function .

Using this algorithm is possible to “solve” the first step of The Solution ( also explained in Implementing the Solution ) .

The main idea is to run all the programs in increasing length and decreasing execution steps until you find the correct program , the drawback is the exponential resource requirement .

The first optimization is due to Levin with a complexity of  (2^(K(T)+1) ) *t(n) and then with Juergen Schmidhuber in “The Speed Prior” paper.

Despite the improvements nowadays the constant is again exponential and the time consumption by this algorithm is a big problem.

Advertisements

One thought on “The Inverse Levin Search

  1. Pingback: Last Kurzweil book : How to create a mind « 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