Techniques of Admissible Recursion Theory
- PDF / 12,905,418 Bytes
- 223 Pages / 468 x 684 pts Page_size
- 10 Downloads / 238 Views
1106
C.l Chong
Techniques of Admissible Recursion Theory
Springer-Verlag Berlin Heidelberg New York Tokyo 1984
Lecture Notes in Mathematics Edited by A. Oold and B. Eckmann Subseries: Harvard/MIT Adviser: G. Sacks
1106
C.l Chong
Techniques of Admissible Recursion Theory
Springer-Verlag Berlin Heidelberg New York Tokyo 1984
Author
Chi-Tat Chong Department of Mathematics, National University of Singapore Kent Ridge, Singapore 0511, Singapore
AMS Subject Classification (1980): 03060,03025 ISBN 3-540-13902-8 Springer-Verlag Berlin Heidelberg New York Tokyo ISBN 0-387-13902-8 Springer-Verlag New York Heidelberg Berlin Tokyo
This work IS subject to copyright. All rights are reserved, whether the whole or part of the material is concerned, specifically those of translation, reprinting, re-use of illustrations, broadcasting, reproduction by photocopying machine or similar means, and storage in data banks. Under § 54 of the German Copyright Law where copies are made for other than private use, a fee is payable to "Verwertungsgesellschaft Wort", Munich.
© by Springer-Verlag Berlin Heidelberg 1984 Printed in Germany Printing and binding: Beltz Offsetdruck, Hemsbach/Bergstr. 2146/3140-543210
FOREWORD
The generalization of recursion theory on the set w of natural numbers to infinite ordinals (now known as higher recursion theory) has a complicated history.
The guiding principle was that basic notions
such as computation, finiteness, recursion, recursiveness, relative recursiveness and effectiveness, which lie at the heart of the subject of classical recursion theory, should not be confined to the consideration of w (and hence countable structures) alone.
Indeed in various
parts of mathematical logic one had encountered notions and procedures which reminded one of effective computability in the generalized sense. however,
In order to develop a reasonable higher recursion theory, it was necessary to have a good intuition of the roles played
by objects such as finite sets and r.e. sets in the classical setting.
Thus for example in Kreisel [1971]
it is aptly pointed out
why in any reasonable generalization of recursion theory the notion of 'finiteness' ought to be central.
As early as 1938, Kleene had
introduced the idea of ordinal notations for natural numbers.
This
made it possible to discuss certain countably infinite ordinals (the recursive ordinals) in terms of the natural numbers they denote.
In
the 1950's and early 1960's various recursiontheoretic results on ChurchKleene wI (wICK), the least nonrecursive ordinal, were derived, leading to the belief that a recursion theory on this ordinal (later christened 'metarecursion theory' by Kreisel and Sacks) could be developed modelled after classical recursion theory.
In particular
there should be a correct analog of relative recursiveness which would allow a positive solution to Post's problem for wICK subsequently confirmed in Sacks [1966a],
This was
[1966b].
It turns out that Godel's constructible universe L is an ideal
N structure in w
Data Loading...
