search for books and compare prices
Tables of Contents for Computability With Computability and Undecidability-A Timeline
Chapter/Section Title
Page #
Page Count
I The FUNDAMENTALS
Paradoxes
Self-Referential Paradoxes
3
2
Zeno's Paradoxes
5
2
Exercises
6
1
What Do the Paradoxes Mean? (Optional)
Philosophy and Mathematics
7
5
Achilles and the Tortoise Revisited
12
6
Exercises
17
1
Whole Numbers
Counting (Ordinal) vs. Quantity (Cardinal)
18
1
Number is All: √2
19
2
Exercises
20
1
Functions
What Is a Function?
Black boxes
21
1
Domains and ranges
22
1
Functions as rules, functions as collections of ordered pairs
23
1
Terminology and Notation
The λ-notation
24
1
One-one and onto functions
25
1
Composition of functions
26
1
Exercises
27
1
Proofs
What Is a Proof?
28
1
Induction
29
2
Proof by Contradiction (Reductio ad Absurdum)
31
1
Proof by Construction
31
1
Proof by Counterexample
32
1
On Existence Proofs
32
1
The Nature of Proof: Certainty and Existence (Optional)
From ``Mathematical proofs: the genesis of reasonable doubt''
33
2
Gina Bari Kolata
The Introduction to Constructive Formalism
35
1
R.L. Goodstein
Exercises
36
2
Infinite Collections?
How Big Is Infinite?
38
1
Enumerability: The Rationals Are Countable
39
1
The Reals Are Not Countable
40
1
Power Sets and the Set of All Sets
41
3
Exercises
41
3
Hilbert ``On the Infinite'' (Optional)
44
125
Exercises
58
5
II COMPUTABLE FUNCTIONS
Computability
Algorithms
63
1
Generl Criteria for Algorithms
Mal'cev's criteria, from Algorithms and Recursive Functions
64
1
Hermes, from Enumerability, Decidability, Computability
65
3
Numbering
68
1
Algorithm vs. Algorithmic Function
69
1
Approaches to Formalizing Computability
70
2
Exercises
71
1
Turning Machines
Turing on Computability (Optional)
72
3
Descriptions and Examples of Turing Machines
75
3
Turing Machines and Functions
78
7
Exercises
83
2
The Most Amazing Fact and Church's Thesis
The Most Amazing Fact
85
1
Emil L. Post on Computability (Optional)
86
5
Primitive Recursive Functions
Definition by Induction
91
1
The Definition of the Primitive Recursive Functions
Basic (initial) functions
92
1
Basic operations
92
1
An inductive definition of the class of functions
93
1
Examples
The constants
93
1
Addition
94
1
Multiplication
94
1
Exponentiation
94
1
Signature and zero test
95
1
Half
95
1
Predecessor and limited subtraction
95
1
Exercises Part 1
96
1
Other Operations Which Are Primitive Recursive
Addition and multiplication of functions
97
1
Functions defined according to conditions
97
1
Predicates and logical operations
98
1
Bounded minimization
99
1
Existence and universality below a bound
100
1
Iteration
100
1
Simultaneously defined functions
100
1
Course-of-values induction
101
1
Prime Numbers for Codings
101
2
Numbering the Primitive Recursive Functions
103
1
Why Primitive Recursive ≠Computable
104
3
Exercises Part 2
104
3
The Grzegorczyk Hierarchy (Optional)
Hierarchies and Bounded Recursion
107
2
The Elementary Functions
109
1
Iterating Iteration: The Ackermann-Peter Function
The functions ψm and proof by double induction
110
1
Dominating the primitive recursive functions
111
1
The Ackermann--Peter function and nested double recursion
112
2
The Grzegorczyk Hierarchy
114
3
Exercises
115
2
Multiple Recursion (Optional)
The Multiply Recursive Functions
Double recursion
117
1
n-fold recursion
118
1
Diagonalizing the multiply recursive functions
119
1
Recursion on Order Types
119
3
The Least Search Operator
The μ-Operator
122
1
The min-Operator
122
1
The μ-Operator Is a Computable Operation
123
1
Partial Recursive Functions
The Partial Recursive Functions
124
1
Diagonalization and the Halting Problem
125
1
The General Recursive Functions
126
1
Godel on Partial Functions
126
2
Exercises
127
1
Numbering the Partial Recursive Functions
Why and How: The Idea
128
1
Indices for the Partial Recursive Functions
129
1
Algorithmic Classes (Optional)
130
1
The Universal Computation Predicate
131
2
The Normal Form Theorem
133
1
The s-m-n Theorem
134
1
The Fixed Point Theorem
135
4
Exercises
136
3
Listability
Listability and Recursively Enumerable Sets
139
2
Domains of Partial Recursive Functions
141
1
The Projection Theorem
142
2
Exercises
142
2
Turing Machine Computable = Partial Recursive (Optional)
Partial Recursive Implies Turing Machine Computable
144
2
Turing Machine Computable Implies Partial Recursive
146
7
III LOGIC and ARITHMETIC
Propositional Logic
Hilbert's Program Revisited
153
1
Formal Systems
154
1
Propositional Logic
The formal language
154
1
Truth and falsity: truth-tables for the connectives
155
2
Validity
157
1
Decidability of Validity
Checking for validity
157
1
Decidability
158
3
Axiomatizing Propositional Logic
161
3
Proving As a Computable Procedure
164
5
Appendix (Optional)
The Unique Readability Theorem
165
1
The Completeness Theorem for Classical Propositional Logic
166
2
Exercises
168
1
An Overview of First-Order Logic and Godel's Theorems
169
70
First-Order Arithmetic
A Formal Language for Arithmetic
174
3
Variables
174
1
Arithmetic functions and terms
174
1
Numerals in unary notation
175
1
Quantifiers: existence and universality
175
1
The formal language
176
1
The standard interpretation and axiomatizing
177
1
Principles of Reasoning and Logical Axioms
Closed wffs and the rule of generalization
177
2
The propositional connectives
179
1
Substitution for a variable
179
1
Distributing the universal quantifier
179
1
Equality
180
1
More principles?
180
1
The Axiom System Q
The axioms
180
2
On consistency and truth
182
1
∃-Introduction and Properties of =: Some Proofs in Q
182
2
Weakness of System Q
184
1
Proving As a Computable Procedure
185
4
Exercises
186
3
Functions Representatble in Formal Arithmetic
Dispensing with Primitive Recursion
189
3
A digression on number theory
190
1
A characterization of the partial recursive functions
191
1
The Recursive Functions Are Representable in Q
192
7
The Functions Representable in Q Are Recursive
199
1
Representabiliy of Recursive Predicates
200
2
Exercises
201
1
The Undecidability of Arithmetic
Q Is Undecidable
202
1
Theories of Arithmetic
Fragments simpler than Q
203
1
Theories
203
1
Axiomatizable theories
204
1
Functions representable in a theory
204
1
Undecidable theories
205
1
Peano Arithmetic (PA) and Arithmetic
205
5
Exercises
208
2
The Unprovability of Consistency
Self-Reference in Arithmetic: The Liar Paradox
210
2
The Unprovability of Consistency
212
4
Historical Remarks
216
7
Exercises
218
5
IV CHURCH'S THESIS and CONSTRUCTIVE MATHEMATICS
Church's Thesis
History
223
3
A Definition or a Thesis?
On definitions
226
1
Kalmar, from ``An argument against the Plausibility of Church's Thesis''
227
1
A platonist perspective: Godel
228
1
Other examples: definitions or theses?
229
1
On the use of Church's Thesis
230
1
Arguments For and Against
For
231
1
Not every recursive function is computable: theoretical vs. actual computability
232
2
Interpretation of the quantifiers in the thesis/definition
234
1
A paradoxical consequence?
235
2
Interpreting the Evidence
237
2
Exercises
238
1
Constructivist Views of Mathematics
239
34
Intuitionism
L. E. J. Brouwer, from ``Intuitionism and formalism'', 1913
240
6
Modern intuitionism
246
2
Recursive Analysis
248
1
Bishop's Constructivism
Errett Bishop, from Foundations of Constructive Analysis
249
5
Some definitions from Bishop's program
254
1
Criticisms of Intuitionism and Bishop's Constructivism
Paul Bernays on intuitionism
255
1
Nicolas Goodman, from ``Reflections on Bishop's philosophy of mathematics''
256
4
Strict Finitism
D. van Dantzig, ``Is 101010 a finite number?''
260
3
David Isles, from ``Remarks on the notion of standard non-isomorphic natural number series''
263
7
Exercises
270
3
Bibliography
273
8
Glossary and Index of Notation
281
2
Index
283