FOM: more on Nabutovsky and Weinberger and Soare

[Peter Cholak]

I have been asked to reply about the following piece of a post on FOM.  I
am not aware then it was posted.

> 
> Subject: FOM: Urbana thoughts; Soare; Pillay 
> From: Stephen G Simpson <simpson at math.psu.edu> 
> Date: Fri, 16 Jun 2000 17:25:35 -0400 (EDT) 
> 
> Matthew Frank Sun, 11 Jun 2000 10:11:16 -0500 (CDT) writes:
> 
>  > Nabutovsky and Weinberger had needed some new results in
>  > computability (which Soare then provided) for their proofs.
> 
> Ummm, well, ....  My understanding of it (I have been reading up on
> the Nabutovsky/Weinberger stuff) is that Nabutovsky and Weinberger
> originally cited an old theorem about r.e. degrees, the Sacks Density
> Theorem.  But then, after discussing the matter with Soare, they found
> that they could get a slightly better geometrical result by applying a
> much easier, tailor-made theorem about r.e. sets, which Soare
> provided.  The easier theorem, due to Soare (see also Soare's ASL 2000
> abstract), is that there exists a sequence of r.e. sets such that any
> settling-down function for any one of the sets in the sequence
> dominates any recursive function composed with any settling-down
> function for the next set in the sequence.
> 
> This theorem of Soare is much easier because, according to some
> recursion theorists that I asked at ASL 2000, the proof does not need
> a priority argument.  Another vindication of the so-called Simpson's
> Thesis!  [ This is a reference to the discussion of the role of
> priority arguments in applied recursion theory, FOM,
> July/August/September 1999.  See for instance my posting of Wed, 4 Aug
> 1999 19:18:00 -0400 (EDT). ]
> 

I have been looking at the N/W stuff. I am finding it difficult to get a
good understanding of what is going.  Personally I have heard several
talks about it (two by W and one by one of his students) and surely I will
hear more. Clearly more study is needed (for me).  I think Soare gave a
very nice talk on the subject at the ASL meeting. The N/W results are
difficult results and some of them are not completely settled.

Soare's slides are now (partially) available (the diagrams are missing) at
http://www.cs.uchicago.edu/~soare/Geometry/slides.html; also see
http://www.cs.uchicago.edu/~soare/Geometry/Geometry.html for links to the
Nabutovsky/Weinberger papers.  The pages of the slides where the needed
computability theory is mentioned is slides 23-25.

N/W first used the Sacks Density Thm for their results. Then they
(actually just W) came to Soare and asked Soare to provide them with a
"tailor-made" theorem. This "tailor-made" result does provide N/W with a
"better" result.  I cannot judge how much better.  But I would not use the
word "slightly" since N/W asked for and were interested in Soare's result.

Soare told me last spring the proof of his theorem was "easy".  Today I
sat down and thought about the proof.  The proof I came up with was a
priority argument done on a tree with Pi^0_2 branching nodes.  It is a
0''-priority argument.  I see no way this can be improved to a 0'-priority
argument (finite injury).  Sacks density is also a 0''-priority argument.
I would say that Soare's proof is only slightly easier than the tree proof
of Sacks density since what has to be done is more transparent. But I
think only someone with a good working knowledge of the tree method could
call this proof easy.

I am not going to enter another debate about the "Simpson's thesis" (for
those interested I suggest looking at the FOM archives.)  But Soare's
result does not support the "Simpson's thesis".


Best Regards
	      Peter Cholak <Peter.Cholak.1 at nd.edu>
		     http://www.nd.edu/~cholak
------------------------------------------------------------------------
Department of Mathematics	|	Phone: (219) 631-6507
370 Math Building       	|	Fax:   (219) 631-6579
Notre Dame, Indiana 46556-5659	|	Office: 223 CCMB
------------------------------------------------------------------------

PS:  I read FOM in the digest version and I will be away over the weekend,
so if you hope I that will reply further, I suggest send your email both
the FOM list and me.