Fast Computation of Finite and Infinite Strings    Next: FAST: The Most Efficient Up: Temporal Complexity Previous: Temporal Complexity

## 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 nth bit of the string ``11111111...'' will appear as part of ALPHABET's 2n-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 pi denote the i-th possible program. Program p1 is run for one instruction every second step (to simplify things, if the TM has a halt instruction and p1 has halted we assume nothing is done during this step -- the resulting loss of efficiency is not significant for what follows). Similarly, p2 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 nth bit of string ``11111111...'' now will appear after at most O(n) steps (as opposed to at least O(n2n) steps for ALPHABET). Why? Let pk be the fastest algorithm that outputs ``11111111...''. Obviously pk computes the n-th bit within O(n) instructions. Now SIMPLE will execute one instruction of pk every 2-k steps. But 2-k is a positive constant that does not depend on n.

Generally speaking, suppose pk is among the fastest finite algorithms for string x and computes xn 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.    Next: FAST: The Most Efficient Up: Temporal Complexity Previous: Temporal Complexity
Juergen Schmidhuber
2001-01-09

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