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
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^{37})) are S-describable, but most
are not,
as obvious from Cantor's insight [#!Cantor:1874!#].

The prefixes x_{n} of all
,
even of those that are not
S-describable, are computed within at most O(n2^{n}) 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^{n})
time steps to output x_{n} and nothing but x_{n}, 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(n2^{n}) 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.