[FOM] Re: Message from Leonid Levin

[Martin Davis]

Below is another message from non-subscriber Leonid Levin. Subscribers 
should be aware that continued posting of messages from non-subscribers is 
very much against FOM policy. With the permission of the editors, I'm 
making an exception in this case.

Martin
****************************************************************************************************************
This is a follow-up to [FOM] posts discussing my ASL talk based
on my FOCS article ( http://arxiv.org/abs/cs.CC/0203029 ).
In a 7/22 [FOM] msg (posted by Martin Davis) Leonid Levin wrote:
: 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.

In a 7/22 [FOM] msg Stephen Simpson wrote:
: Obviously we can't take this assertion literally, because presumably
: the METHODS ALLOWED could include an oracle for the Halting Problem.

I meant my assertion to be taken literally. I allow everything,
INCLUDING the Oracle, if it still stands in Delphi (I am not sure). Yet,
I would take a grain of salt with any claims the Pythias may make of
being privy to any "insider information," like that in Halting Problem
or my password. If their spiritual exercises are employed to extend U to
all strings of some reasonable length, I would expect a conflict with U.