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 x_n (e.g., O(n³⁷)) are S-describable, but most $x \in B^{\sharp}$ are not, as obvious from Cantor's insight [#!Cantor:1874!#].

The prefixes x_n of all $x \in B^{\sharp}$, even of those that are not S-describable, are computed within at most O(n2ⁿ) 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(n2ⁿ) time steps to output x_n and nothing but x_n, 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(n2ⁿ) 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.

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