Content deleted Content added
Jasper Deng (talk | contribs) →Sub-graphs: clarify a bit Tags: Mobile edit Mobile web edit Advanced mobile edit |
Citation bot (talk | contribs) Added doi-broken-date. | Use this bot. Report bugs. | #UCB_CommandLine Tag: Reverted |
||
Line 37:
=== Hutter search ===
A single algorithm, "Hutter search", can solve any well-defined problem in an asymptotically optimal time, barring some caveats. It works by searching through all possible algorithms (by runtime), while simultaneously searching through all possible proofs (by length of proof), looking for a proof of correctness for each algorithm. Since the proof of correctness is of finite size, it "only" adds a constant and does not affect the asymptotic runtime. However, this constant is so big that the algorithm is entirely impractical.<ref>{{cite arXiv|last=Hutter|first=Marcus|date=2002-06-14|title=The Fastest and Shortest Algorithm for All Well-Defined Problems|eprint=cs/0206022}}</ref><ref>{{Cite journal|last=Gagliolo|first=Matteo|date=2007-11-20|title=Universal search|journal=Scholarpedia|language=en|volume=2|issue=11|pages=2575|doi=10.4249/scholarpedia.2575|doi-broken-date=2024-06-12 |issn=1941-6016|bibcode=2007SchpJ...2.2575G|doi-access=free}}</ref> For example, if the shortest proof of correctness of a given algorithm is 1000 bits long, the search will examine at least 2<sup>999</sup> other potential proofs first.
Hutter search is related to [[Solomonoff's theory of inductive inference|Solomonoff induction]], which is a formalization of Bayesian inference. All [[computable]] theories (as implemented by programs) which perfectly describe previous observations are used to calculate the probability of the next observation, with more weight put on the shorter computable theories. Again, the search over all possible explanations makes this procedure galactic.
| |||