# [FOM] Simpson on the Medvedv lattice

Martin Davis martin at eipye.com
Fri May 23 20:24:55 EDT 2003

```I'd like to bring it to the attention of FOM subscribers an interesting
talk given by Steve Simpson at an Amer Math Soc meeting in Baltimore this
January that has just come to my attention.  The transparencies from that
talk are available on Steve's web site at
http://www.math.psu.edu/simpson/talks/ams0301/
and they are very clear. I'll make a few brief comments, but recommend that
subscribers have a look at the transparencies.

Medvedev's notion of reducibility was introduced by him in 1955; a brief
account is available in Hartley Rogers classic book. As with the other
reducibility notions, an equivalence relation is obtained  by calling a and
b equivalent if each is reducible to the other, and then one speaks of the
corresponding equivalence classes as "degrees".

In his talk, Simpson discusses these Medvedev degrees and contrasts their
structure with that of the much-studied r.e. dgrees. Whereas the r.e
degrees only form an upper semi-lattice, Simpson identifies an important
subset of the the Medvedev degrees (into which the r.e. degrees can be
embedded) that form a distributive lattice.

He also notes that in addition to the Medvedev degrees forming the top and
bottom of this lattice, there are intermediate degrees that can be
identified as precisely the degree of the set of infinite sequences of 0s
an 1's that are random in the sense of Martin-Löf. This is a really neat
and surprising (to me), bringing together two fundamental notions. Simpson
contrasts this situation with the much-studied r.e. degrees, where despite
the plenitude of intermediate degrees, none has turned up which can
similarly be identified as the degree of an important problem occurring in
a different context.

Simpson uses the word "natural" in making this contrast, and I find this
precise. I would love to see a precise definition of what it means for
something in mathematics to be "natural", and while we all do use the word,
short of such a definition, the use is bound to be at least partly
subjective. Someone deeply immersed in the demanding craft of priority
constructions, may find sets of intermediate Turing degree constructed by
those means perfectly "natural". And a debate on this matter is sure to
become about words not concepts. But one can be quite precise in stating
that no one has produced an intermediate r.e. degree about which it can be
said that it is the degree of a decision problem that had been previously
been studied and named.

Martin

Martin Davis
Visiting Scholar UC Berkeley
Professor Emeritus, NYU
martin at eipye.com