[FOM] Intermediate Turing Degrees

Vaughan Pratt pratt at cs.stanford.edu
Tue Aug 31 20:16:05 EDT 2010


On 8/30/2010 4:54 AM, Merlin Carl wrote:
> it is well known that there's a rich structure of Turing
> degrees between 0 and 0`. [...]Is there something like Paris-Harrington
> for intermediate Turing degrees?

In a symmetric world this would have been found in 1996.  (Reasoning: 
give or take a year, Gentzen got his handle on PA in 1936, the 
Friedberg-Muchnik result was 1956, and Paris-Harrington was 1976.)

It's a very nice challenge.  My instinct says it won't happen, my 
experience with my instinct counsels caution.  I'm inclined to overrule 
counsel in this case, if only to spur Harvey to yet greater things.

Vaughan Pratt


More information about the FOM mailing list