[FOM] Complexity of (Universal) Turing Machines

[Vladimir Sazonov]

> 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).



Vladimir Sazonov


      ____________________________________________________________________________________
Be a better friend, newshound, and 
know-it-all with Yahoo! Mobile.  Try it now.  http://mobile.yahoo.com/;_ylt=Ahu06i62sR8HDtDypao8Wcj9tAcJ