Author's Preface

Summary

This book has developed over a number of years. The aim has been to give a unified and coherent account of the many and various parts of general recursion theory.

I have not worked alone. The Recursion Theory Seminar in Oslo has for a number of years been a meeting place for an active group of younger people. Their work and enthusiasm have been an important part of the present project. I am happy to acknowledge my debts to Johan Moldestad, Dag Normann, Viggo Stoltenberg-Hansen and John Tucker. It has been a great joy for me to work together with them.

But there are other debts to acknowledge. The Oslo group learned much of their recursion theory from Peter Hinman who spent the year 1971-72 in Oslo and Peter Aczel who was here for part of the year 1973. Robin Gandy, Yiannis Moschovakis and Gerald Sacks have also in many ways helped to shape our ideas about general recursion theory.

I appreciate the invitation from the Ω-group to write this book for their series. In particular, I would like to thank Gert Müller for his friendship and helpfulness.

Finally, I would like to thank Randi Moller for her expert typing of the manuscript, David Kierstead for his valuable help with the proof-reading, and the printers and publishers for the excellent production of this volume.

Advice to the reader. The book is in principle self-contained, but we expect that any reader would have had some previous exposure to recursion theory, e.g. Rogers [136]. The books by Barwise [11], Hinman [61] and Moschovakis [115, 118] supplement our account, often from a different perspective.

The exposition is organized around a main core which is reasonably complete. This is the general theory of computations. But the main core flowers into a number of side branches intended to show how computation theories connect with and unify other parts of general recursion theory. Here we are less complete and proofs may sometimes be more in the nature of a comment on the basic ideas involved. In the main body of the text and in an Epilogue we have tried to point beyond to open problems and areas of further research.