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|
|Number of pages||6|
|State||Published - Jul 5 2010|