Turing Computability Theory and Applications

Turing's famous 1936 paper introduced a formal definition of a computing machine, a Turing machine. This model led to both the development of actual computers and to computability theory, the study of what machines can and cannot compute. This book presen

  • PDF / 3,136,048 Bytes
  • 289 Pages / 439.42 x 683.15 pts Page_size
  • 33 Downloads / 244 Views

DOWNLOAD

REPORT


Turing Computability Theory and Applications

Theory and Applications of Computability In cooperation with the association Computability in Europe

Series Editors Prof. P. Bonizzoni Università degli Studi di Milano-Bicocca Dipartimento di Informatica Sistemistica e Comunicazione (DISCo) Milan Italy [email protected] Prof. V. Brattka Universität der Bundeswehr München Fakultät für Informatik Neubiberg Germany [email protected] Prof. E. Mayordomo Universidad de Zaragoza Departamento de Informática e Ingeniería de Sistemas Zaragoza Spain [email protected] Prof. P. Panangaden McGill University School of Computer Science Montréal Canada [email protected] Founding Editors: P. Bonizzoni, V. Brattka, S.B. Cooper, E. Mayordomo

More information about this series at http://www.springer.com/series/8819

Books published in this series will be of interest to the research community and graduate students, with a unique focus on issues of computability. The perspective of the series is multidisciplinary, recapturing the spirit of Turing by linking theoretical and real-world concerns from computer science, mathematics, biology, physics, and the philosophy of science. The series includes research monographs, advanced and graduate texts, and books that offer an original and informative view of computability and computational paradigms. Series Advisory Board Samson Abramsky, University of Oxford Eric Allender, Rutgers, The State University of New Jersey Klaus Ambos-Spies, Universität Heidelberg Giorgio Ausiello, Università di Roma, “La Sapienza” Jeremy Avigad, Carnegie Mellon University Samuel R. Buss, University of California, San Diego Rodney G. Downey, Victoria University of Wellington Sergei S. Goncharov, Novosibirsk State University Peter Jeavons, University of Oxford Nataša Jonoska, University of South Florida, Tampa Ulrich Kohlenbach, Technische Universität Darmstadt Ming Li, University of Waterloo Wolfgang Maass, Technische Universität Graz Grzegorz Rozenberg, Leiden University and University of Colorado, Boulder Alan Selman, University at Buffalo, The State University of New York Wilfried Sieg, Carnegie Mellon University Jan van Leeuwen, Universiteit Utrecht Klaus Weihrauch, FernUniversität Hagen Philip Welch, University of Bristol

Robert I. Soare

Turing Computability Theory and Applications

Robert I. Soare Department of Mathematics The University of Chicago Chicago, Illinois, USA

03Dxx (Computability and recursion theory). ISSN 2190-619X ISSN 2190-6203 (electronic) Theory and Applications of Computability ISBN 978-3-642-31932-7 ISBN 978-3-642-31933-4 (eBook) DOI 10.1007/978-3-642-31933-4 Library of Congress Control Number: 2016944469 © Springer-Verlag Berlin Heidelberg 2016 This work is subject to copyright. All rights are reserved by the Publisher, whether the whole or part of the material is concerned, specifically the rights of translation, reprinting, reuse of illustrations, recitation, broadcasting, reproduction on microfilms or in any other physical way, and transmission or information storage an