FOM: recursion/computability/complexity theory
Stephen G Simpson
simpson at math.psu.edu
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
>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