Frontier Search

DOI

10.2991/agi.2010.25How to use a DOI?

Abstract

How to search the space of programs for a code that solves a given problem? Standard asymptotically optimal Universal Search orders programs by Levin complexity, implementing an exponential trade-off between program length and runtime. Depending on the problem, however, sometimes we may have a good reason to greatly favor short programs over fast ones, or vice versa. Frontier Search is a novel framework applicable to a wide class of such trade-offs between program size and runtime, and in many ways more general than previous work. We analyze it in depth and derive exact conditions for its applicability.

Copyright

© 2010, the Authors. Published by Atlantis Press.

Open Access

This is an open access article distributed under the CC BY-NC license (http://creativecommons.org/licenses/by-nc/4.0/).

Download article (PDF)

TY  - CONF
AU  - Yi Sun
AU  - Tobias Glasmachers
AU  - Tom Schaul
AU  - Jürgen Schmidhuber
PY  - 2010/06
DA  - 2010/06
TI  - Frontier Search
BT  - Proceedings of the 3d Conference on Artificial General Intelligence (2010)
PB  - Atlantis Press
SP  - 118
EP  - 123
SN  - 1951-6851
UR  - https://doi.org/10.2991/agi.2010.25
DO  - 10.2991/agi.2010.25
ID  - Sun2010/06
ER  -