Speed Prior S and Algorithm GUESS

A resource-oriented point of view suggests the following postulate.

Postulate 6.1   The cumulative prior probability measure of all x incomputable within time t by the most efficient way of computing everything should be inversely proportional to t.

Since the most efficient way of computing all x is embodied by FAST, and since each phase of FAST consumes roughly twice the time and space resources of the previous phase, the cumulative prior probability of each finite phase should be roughly half the one of the previous phase; zero probability should be assigned to infinitely resource-consuming phases. Postulate 6.1 therefore suggests the following definition.

Definition 6.3 (Speed Prior tex2html_wrap_inline$S$)   Define the speed prior S on B^* as

$$S(x) := \sum_{i=1}^{\infty} 2^{-i} S_i(x);~~ where~ S_i(\lamb... ... 1;~ S_i(x) = \sum_{p \to_i x} 2^{-l(p)} ~for~x \succ \lambda.$$

We observe that S(x) is indeed a semimeasure (compare Def. 4.1):

$$S(x0) + S(x1) + \bar{S}(x) = S(x); ~~where~\bar{S}(x) \geq 0.$$

Since $x \in B^*$ is first computed in PHASE Kt(x) within 2^Kt(x)+1 steps, we may rewrite:

$$S(x) = 2^{-Kt(x)} \sum_{i=1}^{\infty} 2^{-i} S_{Kt(x)+i-1}(x) \leq 2^{-Kt(x)}$$ (47)

S can be implemented by the following probabilistic algorithm for a universal MTM.

Algorithm GUESS:

1. Toss an unbiased coin until heads is up; let i denote the number of required trials; set t:=2ⁱ.

2. If the number of steps executed so far exceeds t then exit. Execute one step; if it is a request for an input bit, toss the coin to determine the bit, and set t:=t/2.

3. Go to 2.

In the spirit of FAST, algorithm GUESS makes twice the computation time half as likely, and splits remaining time in half whenever a new bit is requested, to assign equal runtime to the two resulting sets of possible program continuations. Note that the expected runtime of GUESS is unbounded since $\sum_i 2^{-i} 2^{i}$ does not converge. Expected runtime is countable, however, and expected space is of the order of expected time, due to numerous short algorithms producing a constant number of output bits per constant time interval.

Assuming our universe is sampled according to GUESS implemented on some machine, note that the true distribution is not essentially different from the estimated one based on our own, possibly different machine.

Related links: In the beginning was the code! - Zuse's thesis - Life, the universe, and everything - Generalized Algorithmic Information - Speed Prior - The New AI