FOM: recursion/computability/complexity theory

Stephen G Simpson simpson at
Thu Sep 3 12:15:49 EDT 1998

Stephen Fenner writes in 1 Sep 1998 17:21:00:
 > I wouldn't call the whole of complexity theory a subset of recursion
 > theory by any means, but structural complexity is pretty close.  When a 
 > recursion theorist asks me what complexity theory is about, my short
 > answer is that it studies the fine structure of 0.

and in 3 Sep 1998 10:29:59

 > There are lots of ... very interesting results in complexity that
 > are either direct analogues to statements in recursion theory or
 > are proved using its techniques (e.g., priority arguments).

OK.  So you as a complexity theorist are very interested in recursion
theory, and you see structural complexity theory as being very close
to recursion theory and in some cases applying techniques from
recursion theory.

>From this point of view, don't you find it odd that the upcoming
week-long recursion theory conference being organized by Lempp et al
is apparently not going to have *anything* about complexity theory?
Not even one talk?  The title of the conference is "Computability
Theory and Applications".

It strikes me that your interest in recursion theory may be

-- Steve Simpson

More information about the FOM mailing list