Frontier search

Sun Yi; Tobias Glasmachers; Tom Schaul; Jürgen Schmidhuber

Frontier search

Sun Yi, Tobias Glasmachers, Tom Schaul, Jürgen Schmidhuber

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

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.

Original language	English (US)
Title of host publication	Artificial General Intelligence - Proceedings of the Third Conference on Artificial General Intelligence, AGI 2010
Pages	158-163
Number of pages	6
State	Published - Jul 5 2010
Externally published	Yes

Cite this

@inproceedings{11be76199f454554b2a1052823c6cb2e,

title = "Frontier search",

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.",

author = "Sun Yi and Tobias Glasmachers and Tom Schaul and J{\"u}rgen Schmidhuber",

note = "Generated from Scopus record by KAUST IRTS on 2022-09-14",

year = "2010",

month = jul,

day = "5",

language = "English (US)",

isbn = "9789078677369",

pages = "158--163",

booktitle = "Artificial General Intelligence - Proceedings of the Third Conference on Artificial General Intelligence, AGI 2010",

}

TY - GEN

T1 - Frontier search

AU - Yi, Sun

AU - Glasmachers, Tobias

AU - Schaul, Tom

AU - Schmidhuber, Jürgen

N1 - Generated from Scopus record by KAUST IRTS on 2022-09-14

PY - 2010/7/5

Y1 - 2010/7/5

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

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

UR - http://www.scopus.com/inward/record.url?scp=77954112740&partnerID=8YFLogxK

M3 - Conference contribution

SN - 9789078677369

SP - 158

EP - 163

BT - Artificial General Intelligence - Proceedings of the Third Conference on Artificial General Intelligence, AGI 2010

ER -

Frontier search

Abstract

Other files and links

Fingerprint

Cite this