- Contemporary messages sorted: [ by date ] [ by thread ] [ by subject ] [ by author ] [ by messages with attachments ]

From: <juergen.domain.name.hidden>

Date: Tue, 24 Apr 2001 11:10:32 +0200

Hal, I think you really might want to read some introductory textbook on

logic and formal systems, to check the standard definitions of `proof'

and `theorem.'

BTW, the following remarkable method heavily depends on what's provable.

I believe it will find its way into general computer science textbooks.

-------------------------------------------------------------------------

The fastest and shortest algorithm for all well-defined problems

Marcus Hutter, IDSIA

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 f.

ftp://ftp.idsia.ch/pub/techrep/IDSIA-16-00.ps.gz

-------------------------------------------------------------------------

Juergen Schmidhuber www.idsia.ch

Received on Tue Apr 24 2001 - 02:12:24 PDT

Date: Tue, 24 Apr 2001 11:10:32 +0200

Hal, I think you really might want to read some introductory textbook on

logic and formal systems, to check the standard definitions of `proof'

and `theorem.'

BTW, the following remarkable method heavily depends on what's provable.

I believe it will find its way into general computer science textbooks.

-------------------------------------------------------------------------

The fastest and shortest algorithm for all well-defined problems

Marcus Hutter, IDSIA

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 f.

ftp://ftp.idsia.ch/pub/techrep/IDSIA-16-00.ps.gz

-------------------------------------------------------------------------

Juergen Schmidhuber www.idsia.ch

Received on Tue Apr 24 2001 - 02:12:24 PDT

*
This archive was generated by hypermail 2.3.0
: Fri Feb 16 2018 - 13:20:07 PST
*