Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It only takes a minute to sign up.
Sign up to join this community
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?
Can such machines be built in practice?
Yes. By "machine", Schmidhuber just means "computer program".
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.
