next up previous
Next: Probabilistic Gödel Machine Hardware Up: Discussion Previous: Possible Types of Gödel


Example Applications

Example 3.1 (Maximizing expected reward with bounded resources)  

A robot that needs at least 1 liter of gasoline per hour interacts with a partially unknown environment, trying to find hidden, limited gasoline depots to occasionally refuel its tank. It is rewarded in proportion to its lifetime, and dies after at most 100 years or as soon as its tank is empty or it falls off a cliff etc. The probabilistic environmental reactions are initially unknown but assumed to be sampled from the axiomatized Speed Prior [39], according to which hard-to-compute environmental reactions are unlikely. This permits a computable strategy for making near-optimal predictions [39]. One by-product of maximizing expected reward is to maximize expected lifetime.

Less general, more traditional examples that do not involve significant interaction with an environment are also easily dealt with in the reward-based framework:

Example 3.2 (Time-limited NP-hard optimization)   The initial input to the Gödel machine is the representation of a connected graph with a large number of nodes linked by edges of various lengths. Within given time $T$ it should find a cyclic path connecting all nodes. The only real-valued reward will occur at time $T$. It equals 1 divided by the length of the best path found so far (0 if none was found). There are no other inputs. The by-product of maximizing expected reward is to find the shortest path findable within the limited time, given the initial bias.

Example 3.3 (Fast theorem proving)   Prove or disprove as quickly as possible that all even integers $>2$ are the sum of two primes (Goldbach's conjecture). The reward is $1/t$, where $t$ is the time required to produce and verify the first such proof.

Example 3.4 (Optimize any suboptimal problem solver)   Given any formalizable problem, implement a suboptimal but known problem solver as software on the Gödel machine hardware, and let the proof searcher of Section 2.3 run in parallel.


next up previous
Next: Probabilistic Gödel Machine Hardware Up: Discussion Previous: Possible Types of Gödel
Juergen Schmidhuber 2003-12-11

Back to Goedel machine home page