[FOM] correction to my previous posting

[Martin Davis]

Steve Simpson has explained to my that my previous posting about his work 
confused Medvedev reducibility with Muchnik reducibility. I quote from his 
message (with his permission):

<<Regarding my "neat and surprising" result which you highlighted, an
even better way to highlight it is as follows. Among all Muchnik
degrees of Pi^0_1 sets of positive measure, there is a maximum one.
This formulation is better, because the notion of Pi^0_1 set of
positive measure is more fundamental (and has been studied more) than
the notion of Martin-Lof random sequence.

Incidentally, you spoke of Medvedev reducibility, but my talk was
about Muchnik reducibility. The distinction matters in that: (1) My
"neat and surprising" result (about Martin-Lof randomness, or Pi^0_1
sets of positive measure) holds only for Muchnik reducibility. Slaman
and I have a joint paper showing that it fails for Medvedev
reducibility. (2) My embedding of the r.e. Turing degrees works only
for Muchnik reducibility. For Medvedev reducibility, it is an open
question.

[ The underlying distinction is that Medvedev reducibility is uniform.
P is Medvedev reducible to Q iff there exists a partial recursive
functional F such that, for all Y in Q, F(Y) is in P. Muchnik
reducibility is more general in that it is non-uniform. P is Muchnik
reducible to Q iff, for all Y in Q, there exists X in P such that X is
Turing reducible to Y. ]>>

Martin