• PDF / 23,401,010 Bytes
• 255 Pages / 430.866 x 649.134 pts Page_size
• 102 Downloads / 238 Views

DOWNLOAD

REPORT

---

MATHEMATISCHEN WISSENSCHAFTEN IN EINZELDARSTELLUNGEN MIT BESONDERER BERUCKSICHTIGUNG DER ANWENDUNGSGEBIETE HERAUSGEGEBEN VON

J. L. DOOB· E. HEINZ· F. HIRZEBRUCH E.HOPF· H.HOPF. W.MAAK· S. MAC LANE W.MAGNUS· F.K.SCHMIDT· K.STEIN GESCHAFTSFUHRENDE HERAUSGEBER

B.ECKMANN UND B. L.VAN DER WAERDEN ZURICH

BAND 127

SPRINGER-VERLAG BERLIN HEIDELBERG GMBH 1965

ENUMERABILITY . DECIDABILITY COMPUTABILITY AN INTRODUCTION TO THE THEORY OF RECURSIVE FUNCTIONS BY

HANS HERMES PROFESSOR OF MATHEMATICAL LOGIC AND FOUNDATIONS OF MATHEMATICS, UNIVERSITY OF MUNSTER

TRANSLATED BY

G. T. HERMAN

AND

O. PLASSMANN

1965

SPRINGER-VERLAG BERLIN HEIDELBERG GMBH

Library of Congress Catalog Card Number 65-12556 All rights reserved. No part of this book mqy be reproduced in atry form, by microfilm or a'!)' other means, without written permission from the publishers.

ISBN 978-3-662-11688-3 ISBN 978-3-662-11686-9 (eBook) DOI 10.1007/978-3-662-11686-9 © BY SPRINGER-VERLAG BERLIN HEIDELBERG 1965

ORIGINALLY PUBLISHED BY SPRINGER-VERLAG· BERLIN' HEIDELBERG· NEW YORK IN 1965 SOFTCOVER REPRINT OF THE HARDCOVER 1ST EDITION 1965

Managing Editors: Prof Dr. B. ECKMANN, Eidgenbssische Technische Hochschule Zurich Prof Dr. B. L. VAN DER W AE RDEN, Mathematisches Institut der Universitdt Zurich

PREFACE TO THE ORIGINAL EDITION The task of developing algorithms to solve problems has always been considered by mathematicians to be an especially interesting and important one. Normally an algorithm is applicable only to a narrowly limited group of problems. Such is for instance the Euclidean algorithm, which determines the greatest common divisor of two numbers, or the well-known procedure which is used to obtain the square root of a natural number in decimal notation. The more important these special algorithms are, all the more desirable it seems to have algorithms of a greater range of applicability at one's disposal. Throughout the centuries, attempts to provide algorithms applicable as widely as possible were rather unsuccessful. It was only in the second half of the last century that the first appreciable advance took place. Namely, an important group of the inferences of the logic of predicates was given in the form of a calculus. (Here the Boolean algebra played an essential pioneer role.) One could now perhaps have conjectured that all mathematical problems are solvable by algorithms. However, well-known, yet unsolved problems (problems like the word problem of group theory or Hilbert's tenth problem, which considers the question of solvability of Diophantine equations) were warnings to be careful. Nevertheless, the impulse had been given to search for the essence of algorithms. Leibniz already had inquired into this problem, but without success. The mathematicians of our century however, experienced in dealing with abstract problems and especially in operating with formal languages, were successful. About 1936 several suggestions to make precise the concept of algorithm and related concepts were made at almost the same time (Church's thesis