<ol>
<li><p>Can such machines be built in practice? </p>

<p>Yes. By "machine", Schmidhuber just means "computer program".</p></li>
<li><p>Are they at least feasible in our Universe?</p>

<p>Not in their current form -- the algorithms are too inefficient. </p></li>
</ol>

<p>From a ten thousand meter perspective, Jürgen Schmidhuber (and former students, like Marcus Hutter) have been investigating the idea of combining <a href="http://www.scholarpedia.org/article/Universal_search">Levin search</a> with Bayesian reasoning to work out algorithms for general problem-solving. </p>

<p>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. </p>

<p>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. </p>

<p>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 <em>solve</em> problems by reduction to SAT. </p>

CC BY-SA 3.0
2012-07-07T21:20:10.757Z
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
CC BY-SA 3.0
2012-07-07T21:24:00.190Z
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
CC BY-SA 3.0
2012-07-04T06:15:58.350Z
2012-07-04T06:42:24.453Z
2012-07-04T06:42:24.453Z
Neel Krishnaswami
<p>Recently I stumbled upon quite an interesting theoretical construct. A so called  <a href="http://www.idsia.ch/~juergen/gmsummary.html">Gödel machine</a></p>

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

<p>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. </p>

<p>Can such machines be built in practice? Are they at least feasible in our Universe?</p>

<computability><turing-machines><physics><machine-models><ar.hardware-architecture>
Feasibility of Gödel machines
Dmitry Vyal
# Feasibility of Gödel machines

(Asked by: username_0 on 2012-07-03)

Recently I stumbled upon quite an interesting theoretical construct. A so called [Gödel machine](http://www.idsia.ch/~juergen/gmsummary.html)

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?

**Tags:** computability, turing-machines, physics, machine-models, ar.hardware-architecture

---

## 1 answers

### Answer by username_1 on 2012-07-04. Score: 23 | Accepted answer

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](http://www.scholarpedia.org/article/Universal_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.

> **Comments:**
> **username_0**: 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 :)  
> **username_0**: 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?  

---

