Fast Computation of Finite and Infinite Strings

There are many ways of systematically enumerating all computable objects
or bitstrings. All take infinite time. Some, however, compute individual
strings much faster than others. To see this, first consider the trivial
algorithm ``ALPHABET,'' which simply lists all bitstrings ordered by size
and separated by blanks
(compare Marchal's thesis [#!Marchal:98!#] and Moravec's library of all
possible books [#!Moravec:99!#]). ALPHABET will eventually
create all initial finite segments of all strings. For example, the
*n*th bit of the string ``11111111...'' will appear as part of ALPHABET's
2^{n}-th output string. Note, however, that countably many steps
are *not* sufficient to print any infinite string of countable size!

There are much faster ways though. For instance, the algorithm used in
the previous paper on the computable universes [#!Schmidhuber:97brauer!#]
sequentially computes all computable bitstrings by a particular form of
dovetailing. Let *p*^{i} denote the *i*-th possible program. Program *p*^{1}
is run for one instruction every second step (to simplify things, if the
TM has a halt instruction and *p*^{1} has halted we assume nothing is done
during this step -- the resulting loss of efficiency is not significant
for what follows). Similarly, *p*^{2} is run for one instruction every
second of the remaining steps, and so on.

Following Li and Vitányi [#!LiVitanyi:97!#, p. 503 ff],
let us call this popular dovetailer
``SIMPLE.'' It turns out that SIMPLE actually is the fastest in a certain
sense. For instance, the *n*th bit of string ``11111111...'' now will
appear after at most *O*(*n*) steps (as opposed to at least *O*(*n*2^{n}) steps
for ALPHABET). Why? Let *p*^{k} be the fastest algorithm that outputs ``11111111...''.
Obviously *p*^{k} computes the *n*-th bit within *O*(*n*) instructions.
Now SIMPLE will execute one instruction of *p*^{k} every 2^{-k} steps.
But 2^{-k} is a positive constant that does not depend on *n*.

Generally speaking, suppose *p*^{k} is among the fastest finite algorithms
for string *x* and computes *x*_{n}
within at most *O*(*f*(*n*)) instructions, for all *n*.
Then *x*'s first *n* symbols will appear after at most *O*(*f*(*n*)) steps of SIMPLE.
In this sense SIMPLE essentially computes each string as quickly as
its fastest algorithm, although it is in fact computing all computable
strings simultaneously. This may seem counterintuitive.

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