Him: We have all grown up. Nobody expects a Singularity anytime soon any more, as we used to, 10 years ago.

Me: I haven’t grown up.

Him: I know. But be realistic, we have no idea how brains work, nor do we have any idea of what algorithms might bypass the brain.

Another guy: The Moor’s law alone isn’t enough, we have no idea what to put into these machines or how to program them.

Me: You are both wrong, we have the (Universal!) Levin search, for example.

Him: What is that, another Solomonoff induction or something?

Me: Yes, you could say that.

Him: It’s useless. With it, you’d need exponential resources to solve even a minor problem. Sure it’s possible with an infinite amount of computation, in which case it would be a super-intelligence, but you don’t have unlimited processing power required — so you don’t have anything useful with this Levine search.

Me: It just so happens, that we have the Hutter paper which considers the Levin search.

Him: Who’s Hutter? What’s this paper about?

Me: The paper demonstrates, that if the best possible algorithm to sort a certain list requires N steps, then the Levin search can find this optimal sorting algorithm in 5*N steps. At the most. The same is true for any other algorithm, if the optimal algorithm can do something in a second, you can invent this same algorithm in 5 seconds, at most!

Him: Really? I can’t believe that’s true. That would indeed be a superintelligence. But I don’t think that’s possible. There must be some big constant involved here.

Me: The constant is 5 now, it was much greater before Hutter’s paper. Google it, I’ll not help you there. Even funnier theorems have been proven before, funnier, but none of the same importance, I admit.

Him: If that’s really true, I will change sides. Has anybody implemented at least a portion of the Levin search method, using Hutter’s theorem yet?

Me: Maybe they haven’t, maybe they have, Google it yourself! But you’ll find nothing in either case because if someone *is *using it they probably won’t speak openly about it. For the pure theory, however, Google will bring you enough.

Him: Do you realize what kind of danger the existence of such a possibility could pose?

Me: I don’t share your concerns at all, but you already know that.

### Like this:

Like Loading...

*Related*

Taken at face value, you could use this technique to resolve the P ?= NP problem… well, almost. Just take any NP-complete problem and run Levin search for some polynomial number of steps, if it finds an algorithm for this problem, then P = NP, if it doesn’t… you could try a higher degree polynomial, but if it still doesn’t spit out anything for n^k (k greather than, say, a couple dozen), then P != NP, probably, or actually, the problem isn’t interesting anymore – or especially relevant.

This is one of the reasons why I was pretty sceptical for such a theorem to exist, and it seems I was more or less right to be. Not even delving any deeper than the first couple of google hits brings out this:

“Recently Marcus Hutter was able to derive an even more general optimal search algorithm which actually reduces the constant factor down to less than 5 *(at the expense of introducing an unknown, problem class-specific additive constant)*”

And these kind of constants are usually huge. So it seems we won’t get any free lunch even here, which is actually kind of expected. Intelligent machinery is, after all, much more complex than these simple algorithms… 🙂

You have several points here, worth to address them.

With the Levin’s (or Hutter’s) search, you can’t solve a NP problem in a polynomial time. You can’t do it with quantum computers either in a polynomial time. If the problem is NP. Here we agree.

But you can always find the optimal solution algorithm. Regardless how slow/fast this optimal solution algorithm is. If there is a solution, there is a way to find it! Even NP problems have their solution algorithms. And we can find the best possible, Levin says. Doesn’t matter that it still needs exponential resources, sometimes we have them.

We don’t do the impossible, we don’t do miracles, we only do what’s possible. And there is a lot of possibilities to seize. So many, that they outweighs all the miracles a naive person would wish.

You seem to worry about the additive constant. We will talk about it face to face. For one may feed the stray cats and dogs, may feed hungry children in a distant land, fish in the pond, may feed even the trolls. But one should never feed the competition and speaking about certain things publicly.

Another point you are making is that the intelligence is something more complicated, something inherently different than the simple algorithms.

I am certain it isn’t.