Recursion on the Countable Functionals
- PDF / 8,287,343 Bytes
- 199 Pages / 461 x 684 pts Page_size
- 32 Downloads / 226 Views
811 II
IIIII
Dag Normann
Recursion on the Countable Functionals
Springer-Verlag Berlin Heidelberg New York 1980
Author Dag Normann Institute of Mathematics, The University of Oslo Box 1053 Blindern Oslo 3 Norway
A M S Subject Classifications (1980): 03 D 6 5 ISBN 3-540-10019-9 ISBN 0-387-10019-9
Springer-Verlag Berlin Heidelberg NewYork Springer-Verlag NewYork Heidelberg Berlin
Library of Congress Cataloging in Publication Data. Normann, Dag, 1947- Recursion on the countable functionals. (Lecture notes in mathematics; 811)Bibliography: p. Includes index. 1. Recursiontheory. 2. Computable functions. I. Title. II. Series: Lecture notes in mathematics (Berlin); 8tl. QA3.L28 no. 811.[QA96] 510s [511.3]80-19391 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 the publisher, the amount of the fee to be determined by agreement with the publisher. © by Springer-Verlag Berlin Heidelberg 1980 Printed in Germany Printing and binding: Beltz Offsetdruck, Hemsbach/Bergstr. 2141/3140-543210
Introduction Generalized w~ich has
been
reeursion rapidly
theory
growing
now r e c o g n i z e d
as a d i c i p l i n e
to the natural
numbers
One r e a s o n
order that
in order
one quite
torial
proof
ralized
cal proofs and much classical
concerning
is not
reason and
just
One attempt
the fifties.
Much
finite
als
types
has
strong
been c o n c e r n e d
above.
follows
Kleene
isolated
some of the
in a finite
putation
a subclass
but
mation
about
the f u n o t i o n a l s
closed
under
recursion.
during
that he gave
an import-
general
computation relative
setting.
theory
of h i g h e r
if one wants
recursion
f u n c t i on a l s
recursion
be infinite
funetionals subclass
theory;
may have
from a finite
Kieene
normal
function-
of the g e n e r a l
will
showed
for
to c e r t a i n
for h y p e r d r i t h m e t i c
subbranch
is d e c i d a b l e involved.
by Kleene
theory
of o r d i n a r y
of c o u n t a b l e
the notions
the a l g o r i t h m s
so-called
It is a natural
the value
the motiva-
in the
computations
of the
is to look at
Then
in a more
of g e n e r a l i z e d
of his
numbers,
of arbi-
computations
of the
in gene-
of classi-
on which
done
is
combina-
on f u n c t i o n a l s
on Kleene's
the patterns
finiteness
sequence
tree
with
was
recognized
a successful
In p a r t i c u l a r
funetionals.
done
and
understanding
theory
domains
theory
in
on the natural
and to find what
operating
for r e c u r s i o n
has been
sense.
countable serve
that has been
of the proofs
domains.
of a c o m p u t a t i o n
is a g e n e r a l i z a t i o n
and the r e s e a r c h described
Data Loading...
