[FOM] message from Leonid Levin

[Martin Davis]

Leonid Levin has sent me an email message in which he asked that the 
following remarks be
posted on FOM (although he himself is - unfrotunately - not a subscriber). 
To clarify: the exact reference to the article by Jockusch-Soare, cited by 
Levin as JS, can be found in Steve Simpson's posting of July 14.

Martin

<<My article ( http://arxiv.org/abs/cs.CC/0203029 ) does not state
Theorems 1, 2 in Stephen Simpson's msg (cited below as [SS, T. 1, 2] ).

Yet, I say relevant things and should have cited them.
[SS, T.1] is from [Jockusch, Soare, 1972] (T.5.5 in algorithmic form,
restated as Corollary 6.7 in logic form). My introduction makes similar
comments, citing [Barzdin 1969] who proved an equivalent of [JS, T.5.5].

(As a technicality, I convinced Stephen to take back his assertion that
.99 probability in the comment in my abstract can be replaced with 1.)
But I should have cited [JS], too: they were unaware of Barzdin's
work and also restated the result in terms of formal theories.
I also do not state [SS, T.2] (= [JS, T.5.3]), but it follows from a
corollary to my T.2 and I should have cited it, too. (I cited [DeLeeuw,
Moore, Shannon, Shapiro, 1965] which is weaker than [JS, T.5.3] ).

I am very grateful for this [JS] reference and will include it when I
revise my article. I should add that my results (unlike those discussed
in [SS], [JS] ) are quantitative. Moreover, the property stated in my
Theorem 2 is not known to follow from that in its corollary (even if
both bounds are replaced with just divergence), and is, I think, more
relevant to my informal arguments. Let me state them both:

Below, I is Kolmogorov mutual information, U is a universal partial
recursive predicate, B can be, e.g., the halting problem, i.e. the
extension of U with 0-s. [B_n is its restriction to n-bit inputs.]
Theorem. Let A be any extension of U to a total predicate.
Then I (A_n : B_n) = n - O(log n).

I argue, this growth makes the task impossible, NO MATTER WHAT METHODS
ARE ALLOWED. Formal derivation or random choice are two special cases.

Corollary. No randomized algorithm extends U(x) to all
n-bit strings x with probability > n^4/2^n.>>