** 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