(Footnote 2) The search is done in the order of increasing amount of t/p; here t equals time needed to generate,
and to test the validity, of a trial solution string of concepts and p equals the a priori probability that the string
is a correct solution. The greater the program's a priori probability the greater is its probability of being a correct solution.
In the case of the inv problem,
M(x) = s , a correct solution is any algorithm that can operate on both M(·) and s
to produce x. Levin search is closely related to the CJS of the successful solution strings (see Footnote 3).
Ray's report, 1984, gives an excellent explanation of Levin Search, and a proof of it's
validity: Optimal Sequential Search in Ray's Publications)
(Footnote 3) The CJS (conceptual jump size) of a program z is tz divided by pz where pz is the apriori probability of z and tz is its running time.