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.
The prefixes xn of all
,
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
(or the even worse z from Theorem 3.3) -- recall that the
time for computing
grows faster than any recursive function
of n [#!Chaitin:87!#]. We observe that this result is irrelevant for
FAST which will output
within O(n2n) steps, but only
because it also outputs many other strings besides
-- there
is still no fast way of identifying
among all the outputs.
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.