Zusammenfassung
An algorithm M is described that solves any well-defined problem p
as quickly as the fastest algorithm computing a solution to p, save
for a factor of 5 and low-order additive terms. M optimally distributes
resources between the execution of provably correct p-solving programs
and an enumeration of all proofs, including relevant proofs of program
correctness and of time bounds on program runtimes. M avoids Blum's
speed-up theorem by ignoring programs without correctness proof.
M has broader applicability and can be faster than Levin's universal
search, the fastest method for inverting functions save for a large
multiplicative constant. An extension of Kolmogorov complexity and
two novel natural measures of function complexity are used to show
that the most efficient program computing some function f is also
among the shortest programs provably computing
Nutzer