Universal theories of intelligence

Hutter’s AIXI (or AIξ) is a theoretical algorithm for solving all computable problems of (artificial) intelligence. Queries in AIξ are expressed as sequence prediction problems and operate by comprehensively searching the space of all possible Turing-complete programs. When it finds a program, with maximum likelihood against a Solomonoff prior, that correctly predicts the input sequence, it uses that program to predict outputs. That is, the algorithm uses the shortest program that generates the seen input for predicting unseen inputs. Such an algorithm is universal in the sense that it is a theoretically optimal solution to any computable problem (within a constant factor) but suffers a severe practical limitation in that it is uncomputable (due to the size of the constant factor).

Hutter’s AIXItl is a computable approximation to AIXI that uses the same search procedure but enforces computability by imposing time and space bounds when testing candidate programs. Though AIXItl is theoretically computable, solutions to even trivial problems would require computational resources vastly exceeding real computer systems.

Gödel machines are similar to AIXI in that they are theoretical universal problem solving machines that use proof search to solve problems of intelligence. Gödel machines are self-referential, allowing the system to search not only for a proof of a query but also for possible enhancements to its own programming in order to improve proof speed.