Speed-Based Characterization of the Describable next up previous contents
Next: Enumerable Priors vs FAST Up: Temporal Complexity Previous: FAST: The Most Efficient

Speed-Based Characterization of the Describable

The introduction mentioned that some sets seem describable in a certain sense while most of their elements are not. Although the dyadic expansions of most real numbers are not individually describable, the short algorithm ALPHABET from Section 6.1 will compute all their finite prefixes. However, ALPHABET is unable to print any infinite string using only countable time and storage. Rejection of the notion of uncountable storage and time steps leads to a speed-based definition of describability.

Definition 6.1 (``S-describable'' Objects)   Some $x \in B^{\sharp}$ is S-describable (``S'' for ``Speed'') if it has a finite algorithm that outputs x using countable time and space.

Lemma 6.1   With countable time and space requirements, FAST computes all S-describable strings.

To see this, recall that FAST will output any S-describable string as fast as its fastest algorithm, save for a constant factor. Those x with polynomial time bounds on the computation of xn (e.g., O(n37)) are S-describable, but most $x \in B^{\sharp}$ are not, as obvious from Cantor's insight [#!Cantor:1874!#].

The prefixes xn of all $x \in B^{\sharp}$, even of those that are not S-describable, are computed within at most O(n2n) steps, at least as quickly as by ALPHABET. The latter, however, never is faster than that, while FAST often is. Now consider infinite strings x whose fastest individual finite program needs even more than O(n2n) time steps to output xn and nothing but xn, such as Chaitin's $\Omega$ (or the even worse z from Theorem 3.3) -- recall that the time for computing $\Omega_{n}$ grows faster than any recursive function of n [#!Chaitin:87!#]. We observe that this result is irrelevant for FAST which will output $\Omega_{n}$ within O(n2n) steps, but only because it also outputs many other strings besides $\Omega_{n}$ -- there is still no fast way of identifying $\Omega_{n}$ among all the outputs. $\Omega$ is not S-describable because it is not generated any more quickly than uncountably many other infinite and incompressible strings, which are not S-describable either.

next up previous contents
Next: Enumerable Priors vs FAST Up: Temporal Complexity Previous: FAST: The Most Efficient
Juergen Schmidhuber

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