# [FOM] Complexity of (Universal) Turing Machines

Thu Apr 24 20:33:39 EDT 2008

> From: Andrej Bauer Andrej.Bauer at andrej.com

> Perhaps you should be looking at machines that enumerate all finite
> strings. Of course there will be some pretty simple machines that do
> that, e.g., the one computing the identity function. Not so interesting,
> but perhaps still better.

It is not very clear for me what Steve Gardner has really meant,
but I would complement the above note by Andrej Bauer as follows.

>From the point of view of complexity theory, enumeration of finite
binary strings is better to consider as a computable map from unary
strings to binary. The evident example (related with your) is sequence

B_i (with i unary) = the i-th binary string in the alphabetical order
(empty < 0 < 1 < 00 < 01 < 10 < 11 < 000 < ...).

B_i is easily computable and enumerates all binary strings.

But B_i is AWFULLY SLOW as enumeration of binary strings. Too long
to wait when, say, the string one thousand of zeros 00...0 will
appear in this sequence. Nobody of us (even probably the solar
system or even our galaxy or the World) will be alive to that
"moment" (assuming B_i to be computed physically).

In fact, there exists much faster, even the fastest possible
sequence \xi_i (in Latex notation) among polynomial time computable
sequences (maps of unary to binary strings) which is polynomially
optimal (or universal) in the following sense:

for each polynomil time computable sequence of binary strings
\alpha_i there exists a polynomial time computable transformation
of unary strings p (depending on \alpha) such that

\forall unary i \alpha_i = \xi_{p(i)}.

The similarity (and diffirence) with Kolmogorov's additively optimal
encoding of binary strings by binary strings is evident. See also [2].

Note that B_i is not polynomially optimal.

See more on the definition and using \xi_i in

[1] Vladimir Sazonov, A logical approach to the problem "P=?NP",
in: MFCS'80, Lecture Notes in Computer Science, N88,
Springer, New York, 1980, P.562-575, available in
http://www.csc.liv.ac.uk/~sazonov/papers.html
(with an important correction to [1] also mentioned there).

and

[2] Vladimir Sazonov, An equivalence between polynomial constructivity
of Markov's principle and the equality P=NP, Siberian Advances in
Mathematics, 1991 (Russian original of 1989), v.1, N4, pp. 92-121
(also available by the above URL).