文档介绍：THEORIES OF
PLEXITY
ANNALS OF DISCRETE MATHEMATICS 35
General Editor: Peter L. HAMMER
Rutgers University,New Brunswick, NJ, .
Advisory Editors:
C. BERGE, Universite de Paris, France
M. A. HARRISON, University of California, Berkeley, CA, .
V. KLEE, University of Washington, Seattle, WA, .
J.-H. VAN LINT California Institute of Technology,Pasadena, CA, .
G.-C. ROTA, MassachusettsInstitute of Technology,Cambridge, MA, .
NORTH-HOLLAND -AMSTERDAM NEW YORK 0 OXFORD 0 TOKYO
THEORIES OF
PLEXITY
Cristian CALUDE
Department of Mathematics
University of Bucharest
Bucharest, Rumania
1988
Elsevier Science Publishers ., 1988
All rights reserved. No part of this publication may be reproduced, stored in a retrieval system,
or transmitted, in any form or by any means, electronic, mechanical, photocopying, recording or
otherwise, without the prior permission of the copyright owner.
ISBN: 0 444 70356 X
Publishers:
ELSEVIER SCIENCE PUBLISHERS .
. BOX 1991
1000 BZ AMSTERDAM
HERLANDS
Sole distributors for the Canada:
ELSEVIER SCIENCE PANY, INC.
52 VAN DE R B ILT AV EN U E
NEW YORK, . 10017
.
LIBRARY OF CONGRESS
Library of Congress Cataloging-in-Publication Data
Calude, Cristian. 1952-
Theories plexity / Cristian Calude.
p. cm. -- (Annals of discrete mathematics ; 35)
B1b:iography. p.
Includes indexes.
199; 0-444-70356-X
1. plexity. I. Title. 11. Serfes.
QA267. C34 1988
511--dC19 87-30864
CIP
PRINTED IN HERLANDS
TO ELENA AND ANDREEA
This Page Intentionally Left Blank
PREFACE
During the 1890’s, when PEANO’s five axioms were set afloat, a
great effort was done to establish what functions are or are not what we
call today putable functions. DEDEKIND and PEANO
have been the fvst to use functions defined by induction, an important
preliminary stage of the recursive function theory. The foundational prob-
lems a