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?
Received on Tue Jun 25 2002 - 11:42:35 PDT