On Mon, Jun 17, 2002 at 12:39:49PM +0200, Bruno Marchal wrote: > Recursion theory is the same as Computability Theory, although > the name "recursion theory" is used when the emphasis is on the abstract > theory. Recursion theory has born with Emil Post 1944 paper, which is still > a good introduction. Post paper can be find in Davis "The Undecidable".
I found a 38 page paper on the web (http://www.math.ucla.edu/~asl/bsl/0203/0203-002.ps) about why computability theory is historically called recursion theory, and why we should stop calling it that. I knew that recursive functions are the same as Turing-computable functions, which is a key result of computability/recursion theory. What I didn't realize until recently was how much work has been done on unsolvable problems, for example classifying them according to the degree of unsolvability, and that also falls under the name recursion theory. I'm hoping this theory will offer some insights about what uncomputable universes might be like, and whether we should assign a non-zero probability of being inside a uncomputable universe (i.e. whether there could be uncomputable physical laws). > *The* classical treatise is the book by Hartley Rogers: > > ROGERS H., "Theory of Recursive Functions and Effective Computability", > McGraw-Hill, 1967. (2ed Ed. MIT Press, 1987). I got this book yesterday. It seems to cover everything I want but hasn't been updated since 1967. (The second edition only fixes a few errors.) I wonder what interesting new results I might miss. I assume Odifreddi's book is more up to date, but why is it called "Classical Recursion Theory"? Which parts of recursion theory is considered not classical?