The Fastest and Shortest Algorithm for All Well-Defined Problems (2002)

Marcus Hutter, The Fastest and Shortest Algorithm 4

[14, 16], when handled with care. The same should hold for Theorem 1, as will be

discussed. We avoid the O() notation as far as possible, as it can be severely misleading

(e.g. 1042 =O(1)O(1) =O(1)). This work could be viewed as another O() warning

showing, how important factors, and even subdominant additive terms, are.

An obvious time bound for pis the actual computation time itself. An obvious algorithm

to compute timep(x) is to count the number of steps needed for computing p(x). Hence,

inserting tp=timepinto Theorem 1 and using timetimep(x)≤timep(x), we see that the

computation time of Mp∗is optimal within a multiplicative constant (dp+ 5) and an

additive constant cp. The result is weaker than the one in Theorem 1, but no assumption

concerning the computability of time bounds has to be made.

When do we trust that a fast algorithm solves a given problem? At least for well specified

problems, like satisfiability, solving a combinatoric puzzle, computing the digits of π, ...,

we usually invent algorithms, prove that they solve the problem and in many cases also

can prove good and fast time bounds. In these cases, the provability assumptions in

Theorem 1 are no real restriction. The same holds for approximate algorithms which

guarantee a precision εwithin a known time bound (many numerical algorithms are of

this kind). For exact/approximate programs provably computing/converging to the right

answer (e.g. traveling salesman problem, and also many numerical programs), but for

which no good, and easy to compute time bound exists, Mp∗is only optimal apart from

a huge constant factor 5 + dpin time, as discussed above. A precursor of algorithm Mp∗

for this case, in a special setting, can be found in [8]3. For poorly specified problems,

Theorem 1 does not help at all.

4 The Fast Algorithm Mp∗

One ingredient of algorithm Mp∗is an enumeration of proofs of increasing length in some

formal axiomatic system. If a proof actually proves that pand p∗are functionally equiv-

alent and phas time bound tp, add (p, tp) to a list L. The program pin Lwith the

currently smallest time bound tp(x) is executed. By construction, the result p(x) is iden-

tical to p∗(x). The trick to achieve the time bound stated in Theorem 1 is to schedule

everything in a proper way, in order not to lose too much performance by computing slow

p’s and tp’s before the phas been found.

To avoid confusion, we formally define pand tpto be binary strings. That is, pis neither

a program nor a function, but can be informally interpreted as such. A formal definition

of the interpretations of pis given below. We say “p computes function f ”, when a

universal reference Turing machine Uon input (p, x) computes f(x) for all x. This is

denoted by U(p, x)=f(x). To be able to talk about proofs, we need a formal logic system

(∀, λ, yi, ci, fi, Ri,→,∧,=, ...), and axioms, and inference rules. A proof is a sequence of

formulas, where each formula is either an axiom or inferred from previous formulas in the

3The algorithm AIξtl creates an incremental policy for an agent in an unknown non-Markovian

environment, which is superior to any other time tand space lbounded agent. The computation time of

AIξtl is of the order t·2l.

from Hacker News https://ift.tt/3uo8W4h