Re: recursion theory

From: Bruno Marchal <marchal.domain.name.hidden>
Date: Mon, 17 Jun 2002 12:39:49 +0200

At 2:20 -0700 16/06/2002, Wei Dai wrote:
>I'm trying to learn about recursive ordinals and related topics such as
>the arithmetical hierarchy, which are studied under the name "recursion
>theory". Is anyone here familiar with recursion theory? Can anyone
>recommend a book on it?


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".

*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).

Another treatise is the Noth-Holland 1989 (Amsterdam) book by Odifreddi P:
"Classical recursion Theory". (Big, deep, historically sound, ...).

A very nice and readable introduction I would recommend is the book by
Neil Cutland:

CUTLAND N., Computability, "An Introduction to Recursive Function Theory",
Cambridge University Press, 1980.

Recursion theory is very near metamathematics. It is also necessary
for extending the G and G* logics to the extensions with quantifiers.

About Recursive Ordinals a good paper is the rewriting by Feferman of
Turing's founding paper on that subject:

FEFERMAN S., 1988, Turing in the land of O(z), in the book edited by
Herken: "The Universal Turing Machine A half century survey", Oxford
University Press, 1988.

There is also a short concise somehow abrupt introduction to Rec Th by
Shoenfield. Springer Verlag Lecture Note in mathematical Logic n°1.

But the book by CUTLAND is the best intro for the non mathematical
logician, imo.

Bruno
Received on Mon Jun 17 2002 - 03:38:59 PDT