Computation with External Help
According to the Computability Thesis, all models of computation, including those yet to be discovered, are equivalent to the Turing machine and formalize the intuitive notion of computation. In other words, what cannot be solved on a Turing machine canno
- PDF / 6,968,448 Bytes
- 428 Pages / 439.371 x 683.151 pts Page_size
- 37 Downloads / 215 Views
The Foundations of Computability Theory Second Edition
The Foundations of Computability Theory
Borut Robič
The Foundations of Computability Theory Second Edition
Borut Robič Faculty of Computer and Information Science University of Ljubljana Ljubljana, Slovenia
ISBN 978-3-662-62420-3 ISBN 978-3-662-62421-0 (eBook) https://doi.org/10.1007/978-3-662-62421-0 © Springer-Verlag GmbH Germany, part of Springer Nature 2015, 2020 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 and retrieval, electronic adaptation, computer software, or by similar or dissimilar methodology now known or hereafter developed. The use of general descriptive names, registered names, trademarks, service marks, etc. in this publication does not imply, even in the absence of a specific statement, that such names are exempt from the relevant protective laws and regulations and therefore free for general use. The publisher, the authors, and the editors are safe to assume that the advice and information in this book are believed to be true and accurate at the date of publication. Neither the publisher nor the authors or the editors give a warranty, expressed or implied, with respect to the material contained herein or for any errors or omissions that may have been made. The publisher remains neutral with regard to jurisdictional claims in published maps and institutional affiliations. This Springer imprint is published by the registered company Springer-Verlag GmbH, DE part of Springer Nature. The registered company address is: Heidelberger Platz 3, 14197 Berlin, Germany
To Marinka, Gregor and Rebeka Hana
I still think that the best way to learn a new idea is to see its history, to see why someone was forced to go through the painful and wonderful process of giving birth to a new idea. . . . Otherwise, it is impossible to guess how anyone could have discovered or invented it. — Gregory J. Chaitin, Meta Maths, The Quest for Omega
Preface
Context The paradoxes discovered in Cantor’s set theory sometime around 1900 began a crisis that shook the foundations of mathematics. In order to reconstruct mathematics, freed from all paradoxes, Hilbert introduced a promising program with formal systems as the central idea. Though the program was unexpectedly brought to a close in 1931 by G¨odel’s famous theorems, it bequeathed burning questions: “What is computing? What is computable? What is an algorithm? Can every problem be algorithmically solved?” This led to Computability Theory, which was born in the mid-1930s, when these questions were resolved by the seminal works of Church, G¨odel, Kleene, Post, and Turing. In addition to contributing to some of the greatest advances of twentieth-century mathematics, their ideas laid the foundations for the practical development of a
Data Loading...
