FOM: lurking issues in recursion theory

[Piergiorgio Odifreddi]

a propos of the issues raised by shipman and simpson, some interesting
foundational work HAS been done in recursion theory! i'll give two
examples.

1) post's simple set was proved to be m-incomplete by post himself,
independently of the acceptable system of indices used in its
construction. and it turns out to be T-complete, again independently.
but, most interestingly, it maybe tt-complete or tt-incomplete,
w.r.t. different acceptable systems of indices. this has been proved
by lachlan (see my book, volume I, pp. 271-272 and 346-347).

a similar situation arises for post's hypersimple set, which is always
tt-incomplete, but can be T-complete or T-incomplete w.r.t. different
acceptable systems of indices. ironically (due to the ongoing diatribe,
which shows little sense of humour), this has been proved in the early
70s by jockusch and SOARE. 

2) minimal turing degrees were originally constructed by spector using
trees. a methodological analysis shows that they cannot be constructed
by finite extensions as in the early arguments by kleene and post
but can be constructed by coinfinite recursive extensions, which are
more stringent than simple trees. this result is due to lachlan, again
(see volume I of my book, pp. 479 and 520-523).

this shows that recursion theorists have been interested (admittedly,
sporadically) in foundational and methodological issues. i wish more
work had been done in these areas, but i have tried to report as much
as possible in my book. and one of the major open problems in the
area is the socalled "invariant solution to post's problem", posed by
sacks (who is generally regarded as insensitive to foundational issues),
and asking for a solution that relativizes to any oracle. the status of
the progress on the problem is reported in my volume II, pp. 510-511,
where i discuss precisely the naturality of the various solutions to
post's problem found through the years.

george odifreddi

ps. i hope i'm forgiven the references to my book, but it is easier
for me to provide references to it than to quote original papers.