Recursion Theory and Computational Complexity : Lectures Given at a Summer School of the Centro Internazionale Matematico Estivo (C.I.M.E.) Held in Bressanone (Bolzano), Italy, June 14-23, 1979

S. Homer: Admissible recursion theory.- B.E. Jacobs: Computational complexity and recursion theory.- D. Normann: A survey of set recursion.- G.E. Sacks: Priority arguments in Higgler recursion.- R.I. Soare: Construction in the recursively enumerable degrees.- W. Maass: Recursively invariant recursion theory. Many mathematicians from all over the world have been involved in a way or another in C.I.M.E.'s activities over the years. The main purpose and mode of functioning of the Centre may be summarised as follows: every year, during the summer, sessions on different themes from pure and applied mathematics are offered by application to mathematicians from all countries. A Session is generally based on three or four main courses given by specialists of international renown, plus a certain number of seminars, and is held in an attractive rural location in Italy The aim of a C.I.M.E. session is to bring to the attention of younger researchers the origins, development, and perspectives of some very active branch of mathematical research. The topics of the courses are generally of international resonance. The full immersion atmosphere of the courses and the daily exchange among participants are thus an initiation to international collaboration in mathematical research. --Book Jacket Front Matter....Pages i-iii Admissible Recursion Theory....Pages 5-28 Computational Complexity and Recursion Theory....Pages 29-98 A Survey of Set Recursion....Pages 99-106 Priority Arguments in Higher Recursion Theory....Pages 107-168 Constructions in the Recursively Enumerable Degrees....Pages 169-225 Recursively Invariant -Recursion Theory....Pages 227-240 C.I.M.E. stands for Centro Internazionale Matematico Estivo, that is, International Mathematical Summer Centre. Conceived in the early fifties, it was born in 1954 in Florence, Italy, and welcomed by the world mathematical community: it continues successfully, year for year, to this day