[FOM] message from Leonid Levin

[Stephen G Simpson]

This is a follow-up to Leonid Levin's message which Martin Davis
posted on FOM, Tue, 22 Jul 2003 10:53:46 -0700.  It is a pity that
Levin refuses to subscribe to FOM and engage in direct discussion of
his provocative remarks which Martin posted on FOM for him, at his
request.

Martin Davis (quoting Levin) writes:

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

Obviously we can't take this assertion literally, because presumably
the METHODS ALLOWED could include an oracle for the Halting Problem.
So, what is Levin really saying here?  Is the result merely technical?
Or, is there a way to explain the result in precise but intuitively
understandable terms, which would be appropriate for the FOM list?
What computational methods does Levin have in mind, beyond "formal
derivation" and "random choice"? [ I assume that these quoted phrases
refer to Turing computation using a random sequence of 0's and 1's as
a Turing oracle, as made precise in my earlier posting.  Is this
correct? ]

Stephen G. Simpson
Professor of Mathematics
Pennsylvania State University