Next: Probabilistic Gödel Machine Hardware Up: Discussion & Previous Work Previous: Possible Types of Gödel

## Example Applications

Traditional examples that do not involve significant interaction with a probabilistic environment are easily dealt with in our reward-based framework:

Example 6.1 (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 it should find a cyclic path connecting all nodes. The only real-valued reward will occur at time . 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 6.2 (Fast theorem proving)   Prove or disprove as quickly as possible that all even integers are the sum of two primes (Goldbach's conjecture). The reward is , where is the time required to produce and verify the first such proof.

More general cases are:

Example 6.3 (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 [43], according to which hard-to-compute environmental reactions are unlikely. This permits a computable strategy for making near-optimal predictions [43]. One by-product of maximizing expected reward is to maximize expected lifetime.

Example 6.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 5 run in parallel.

Next: Probabilistic Gödel Machine Hardware Up: Discussion & Previous Work Previous: Possible Types of Gödel
Juergen Schmidhuber 2005-01-03