Bias-Optimality

We will consider a very broad class of problems. A problem is defined by a recursive procedure that takes as an input any potential solution (a finite symbol string , where represents a search space of solution candidates) and outputs 1 if is a solution to , and 0 otherwise. Typically the goal is to find as quickly as possible some that solves .

Define a probability distribution on a finite or infinite
set of programs for a given computer. represents the searcher's initial bias
(e.g., could be based on program length, or on a probabilistic syntax diagram).
A *bias-optimal* searcher will not spend more
time on any solution candidate than it deserves,
namely, not more than the candidate's probability times the total search time:

Back to OOPS main page