Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Recently I stumbled upon quite an interesting theoretical construct. A so called Gödel machine

It's a general problem solver which is capable of self-optimization. It's suitable for reactive environments.

As I understand, it can be implemented as a program for universal Turing machine, although it's requirements go far beyond hardware currently available. I couldn't find many details, though.

Can such machines be built in practice? Are they at least feasible in our Universe?

share|cite|improve this question
up vote 20 down vote accepted
  1. Can such machines be built in practice?

    Yes. By "machine", Schmidhuber just means "computer program".

  2. Are they at least feasible in our Universe?

    Not in their current form -- the algorithms are too inefficient.

From a ten thousand meter perspective, Jürgen Schmidhuber (and former students, like Marcus Hutter) have been investigating the idea of combining Levin search with Bayesian reasoning to work out algorithms for general problem-solving.

The basic idea behind Levin search is that it's possible to use dovetailing and Goedel codes to give a single algorithm which is, up to constant factors, optimal. Loosely, you fix a Godel encoding of programs, and then run a Turing machine that runs the $n$-th program once every $2^{n}$ steps. This means that if the $n$-th program is optimal for some problem, then Levin search will "only" be a constant factor of $2^n$ times slower.

They have done a fair amount of work on making the constant factors less stupendously, horrifically awful, and are optimistic that this kind of scheme can work in practice. I am (based on my experience in automated theorem proving) very skeptical, since good data structures are critical to theorem proving, and Goedel encodings are terrible data structures.

But you don't know it can't work until you try to make it work! After all, we already live in a world where people solve problems by reduction to SAT.

share|cite|improve this answer
Thanks for a perfect summary! I've read through the whole chapter devoted to Gödel machines in an Artificial General Intelligence book. Looks like the author hid the forest behind the trees :) – Dmitry Vyal Jul 7 '12 at 21:20
By the way, if the number n of an optimal program isn't known in advance, is it correct to call these machines optimal up to a constant factor? – Dmitry Vyal Jul 7 '12 at 21:24

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.