β Scribed by Richard L. Epstein, Walter A. Carnielli
No coin nor oath required. For personal study only.
Now in a new edition!--the classic presentation of the theory of computable functions in the context of the foundations of mathematics. Part I motivates the study of computability with discussions and readings about the crisis in the foundations of mathematics in the early 20th century, while presenting the basic ideas of whole number, function, proof, and real number. Part II starts with readings from Turing and Post leading to the formal theory of recursive functions. Part III presents sufficient formal logic to give a full development of G?del's incompleteness theorems. Part IV considers the significance of the technical work with a discussion of Church's Thesis and readings on the foundations of mathematics. This new edition contains the timeline "Computability and Undecidability" as well as the essay "On mathematics".
Title......Page 2
Contents......Page 4
Preface......Page 10
01 Paradoxes......Page 16
02 What do the Paradoxes Mean......Page 20
03 Whole Numbers......Page 31
04 Functions......Page 34
05 Proofs......Page 41
06 Infinite Collections?......Page 51
07 Hilbert "On the Infinite"......Page 57
08 Computability......Page 76
09 Turing Machines......Page 85
10 The Most Amazing Fact And Church's Thesis......Page 98
11 Primitive Recursive Functions......Page 104
12 The Grzegorczyk Hierarchy......Page 120
13 Multiple Recursion......Page 130
14 The Least Search Operator ......Page 135
15 Partial Recursive Functions......Page 137
16 Numbering the Partial Recursive Functions......Page 141
17 Listability......Page 152
18 Turing Machine Computable = Partial Recursive......Page 157
19 Propositional Logic......Page 164
20 An Overview of First-Order Logic and Goedel's Theorems......Page 180
21 First-Order Arithmetic......Page 185
22 Functions Representable in Formal Arithmetic......Page 200
23 The Undecidability of Arithmetic......Page 213
24 The Unprovability of Consistency......Page 221
25 Church's Thesis......Page 232
26 Constructivist Views of Mathematics......Page 248
27 Mathematics as Modeling......Page 282
Computability and Undecidability - A Timeline......Page 313
Bibliography......Page 341
Glossary and Index of Notation......Page 359
Index......Page 361
π SIMILAR VOLUMES
Now in a new edition!--the classic presentation of the theory of computable functions in the context of the foundations of mathematics. Part I motivates the study of computability with discussions and readings about the crisis in the foundations of mathematics in the early 20th century, while pre
Now in a new edition!--the classic presentation of the theory of computable functions in the context of the foundations of mathematics. Part I motivates the study of computability with discussions and readings about the crisis in the foundations of mathematics in the early 20th century, while pre
Now in a new edition!--the classic presentation of the theory of computable functions in the context of the foundations of mathematics. Part I motivates the study of computability with discussions and readings about the crisis in the foundations of mathematics in the early 20th century, while pre
<p>This book presents a set of historical recollections on the work of Martin Davis and his role in advancing our understanding of the connections between logic, computing, and unsolvability. The individual contributions touch on most of the core aspects of Davisβ work and set it in a contemporary c