List of Figures xvi
Preface xviii
About the Companion Website xx
<b>Part I Philosophy and Computer Science 1</b>
<b>1 An Introduction to the Philosophy of Computer Science 3</b>
1.1 What This Book Is About 3
1.2 What This Book Is Not About 5
<b>2 Philosophy: A Personal View 7</b>
2.1 Introduction 7
2.2 A Definition of 'Philosophy' 8
2.3 What Is Truth? 9
2.3.1 Correspondence Theories of Truth 10
2.3.2 Coherence Theories of Truth 10
2.3.3 Correspondence vs. Coherence 10
2.4 Searching for the Truth 13
2.4.1 Searching vs. Finding 13
2.4.2 Asking "Why?" 14
2.4.3 Can There Be Progress in Philosophy? 15
2.4.4 Skepticism 16
2.5 What Is "Rational"? 17
2.5.1 Logical Rationality 17
2.5.2 Scientific Rationality 20
2.5.3 Computational Rationality 21
2.5.4 Is It Always Rational to Be Rational? 21
2.6 Philosophy as a Personal Search 22
2.7 Philosophies of Anything and Everything 23
2.8 Philosophy and Computer Science 25
2.9 Appendix: Argument Analysis and Evaluation 25
2.9.1 Introduction 25
2.9.2 A Question-Answer Game 26
2.9.3 Missing Premises 27
2.9.4 When Is an Argument a "Good" Argument? 30
2.9.5 Examples of Good and Bad Arguments 34
2.9.6 Summary 35
<b>Part II Computer Science, Computers, and Computation 37</b>
<b>3 What Is Computer Science? 39</b>
3.1 Introduction 39
3.2 Naming the Discipline 39
3.3 Why Ask What CS Is? 40
3.4 What Does It Mean to Ask What Something Is? 42
3.4.1 Determining Boundaries 42
3.4.2 Extensional and Intensional Definition 45
3.5 CS as the Science of Computers 47
3.5.1 Objection: Computers Are Not Natural 48
3.5.2 Objection: Computers Are Tools, Not Phenomena 49
3.5.3 Digression: The Once-upon-a-Time Science of Microscopy 51
3.5.4 Objection: CS Is Just a Branch of ... 52
3.5.5 Objection: What about Algorithms? 52
3.6 CS Studies Algorithms 53
3.6.1 Only Algorithms? 53
3.6.2 Or Computers, Too? 55
3.7 Physical Computers vs. Abstract Algorithms 56
3.8 CS Studies Information 57
3.9 CS as a Mathematical Science 58
3.10 CS as a Natural Science of Procedures 61
3.11 CS as an Empirical Study 63
3.12 CS as Engineering 64
3.13 Science xor Engineering? 66
3.14 CS as "Both" 66
3.15 CS as "More" 68
3.15.1 CS as a New Kind of Science 68
3.15.2 CS as a New Kind of Engineering 70
3.16 CS as "Neither" 71
3.16.1 CS as Art 71
3.16.2 CS as the Study of Complexity 71
3.16.3 CS as the Philosophy(!) of Procedures 72
3.16.4 CS as Computational Thinking 72
3.16.5 CS as AI 73
3.16.6 Is CS Magic? 74
3.17 Summary 76
3.18 Questions for the Reader 77
<b>4 Science 78</b>
4.1 Introduction 78
4.2 Science and Non-Science 79
4.3 Science as Systematic Study 80
4.4 The Goals of Science 81
4.4.1 Description 81
4.4.2 Explanation 82
4.4.3 Prediction 82
4.5 Instrumentalism vs. Realism 83
4.6 Scientific Theories 85
4.7 "The" Scientific Method 86
4.8 Falsifiability 88
4.8.1 Science as Conjectures and Refutations 88
4.8.2 The Logic of Falsifiability 89
4.8.3 Problems with Falsifiability 90
4.9 Scientific Revolutions 90
4.10 Other Alternatives 91
4.11 CS and Science 91
4.11.1 Is CS a Science? 91
4.11.2 What Kind of Science Might CS Be? 92
4.12 Questions to Think About 93
<b>5 Engineering 95</b>
5.1 Defining 'Engineering' 95
5.2 Engineering as Science 97
5.3 A Brief History of Engineering 98
5.4 Conceptions of Engineering 99
5.5 What Engineers Do 100
5.5.1 Engineering as Design 100
5.5.2 Engineering as Building 100
5.6 The Engineering Method 101
5.7 Software Engineering 102
5.8 CS and Engineering 104
5.9 Questions to Think About 105
<b>6 Computers: A Brief History 107</b>
6.1 Introduction 107
6.2 Would You Like to Be a Computer? 108
6.3 Two Histories of Computers 109
6.4 The Engineering History 109
6.4.1 Ancient Greece 109
6.4.2 Seventeenth Century Calculating Machines 110
6.4.3 Babbage's Machines 110
6.4.4 Electronic Computers 111
6.4.5 Modern Computers 112
6.5 The Scientific History 113
6.6 The Histories Converge 116
6.7 What Is a Computer? 116
6.7.1 An Engineering Answer 116
6.7.2 A Scientific Answer 117
<b>7 Algorithms and Computability 119</b>
7.1 Introduction 119
7.2 Functions and Computation 120
7.2.1 Mathematical Functions 120
7.2.2 Functions Described Extensionally 121
7.2.3 Functions Described Intensionally 123
7.2.4 Function "Machines" 125
7.2.5 Computable Functions 126
7.3 'Algorithm' Made Precise 128
7.3.1 Ancient Algorithms 128
7.3.2 "Effectiveness" 128
7.3.3 Three Attempts at Precision 129
7.4 Five Great Insights of CS 134
7.4.1 Insight 1: Representation 134
7.4.2 Insight 2: Processing 135
7.4.3 Insight 3: Structure 136
7.4.3.1 Structured Programming (I) 136
7.4.3.2 Digression - Recursive Definitions 137
7.4.3.3 Structured Programming (II) 138
7.4.4 Insight 4: The Church-Turing Computability Thesis 139
7.4.5 Insight 5: Implementation 141
7.5 Structured Programming 142
7.5.1 Basic Programs 142
7.5.2 Program Constructors 143
7.5.3 Classification of Structured Programs 144
7.6 Recursive Functions 144
7.6.1 A Recursive Definition of Natural Numbers 144
7.6.2 Recursive Definitions of Recursive Functions 145
7.6.3 Classification of Recursive Functions 149
7.7 Non-Computable Functions 150
7.7.1 The Halting Problem 150
7.7.2 Proof Sketch that H Is Not Computable 153
7.8 Summary 155
7.9 Questions for the Reader 155
<b>8 Turing's Analysis of Computation 157</b>
8.1 Introduction 157
8.2 Slow and Active Reading 158
8.3 Title: "The Entscheidungsproblem" 158
8.4 Paragraph 1 159
8.4.1 " 'Computable' Numbers" 159
8.4.2 "Written By a Machine" 160
8.5 Paragraph 2 160
8.5.1 "Naturally Regarded as Computable" 160
8.5.2 "Definable Numbers" 161
8.6 Section 1, Paragraph 1: "Computing Machines" 161
8.7 Section 9: "The Extent of the Computable Numbers" 162
8.7.1 Turing's Computability Thesis 162
8.7.2 "Writing Symbols on Paper" 163
8.7.3 States of Mind 166
8.7.4 Operations 167
8.7.5 Another "Simple Operation" 169
8.7.6 "Immediate Recognisability" 169
8.7.7 Summary of Operations 170
8.7.8 "States of Mind" 170
8.7.9 Turing Machines, Turing's Thesis, and AI 172
8.8 "Computing Machines" 174
8.8.1 "Man" and "Machine" 175
8.8.2 Closure Clause: Turing's Thesis 178
8.9 Section 2: "Definitions" 178
8.9.1 "Automatic Machines" 178
8.9.2 "Choice Machines" 179
8.9.3 "Computing Machines" 179
8.9.4 "Complete Configurations" 180
8.9.5 "Circular and Circle-Free Machines" 181
8.9.6 "Circular" Machines 182
8.9.7 "Computable Sequences and Numbers" 183
8.10 Section 3: "Examples of Computing Machines" 184
8.10.1 Example I 184
8.10.2 Example II, Paragraph 1 189
8.10.3 Example II, Paragraph 2 192
8.11 Section 4: "Abbreviated Tables" 195
8.12 Section 5: "Enumeration of Computable Sequences" 196
8.13 Section 6: "The Universal Computing Machine" 201
8.14 The Rest of Turing's Paper 203
<b>9 Computers: A Philosophical Perspective 204</b>
9.1 What Is a Computer? 204
9.2 Informal Definitions 206
9.2.1 Reference-Book Definitions 206
9.2.2 John von Neumann's Definition 206
9.2.3 Arthur Samuel's Definition 207
9.2.4 Martin Davis's Characterization 208
9.2.5 Summary 208
9.3 Computers, Turing Machines, and Universal Turing Machines 210
9.3.1 Computers as Turing Machines 210
9.3.2 Stored Program vs. Programmable 211
9.4 John Searle's "Pancomputationalism": Everything Is a Computer 212
9.4.1 Searle's Argument 212
9.4.2 Computers Are Described in Terms of 0s and 1s 213
9.4.3 Being a Computer Is a Syntactic Property 214
9.4.4 Being a Computer Is Not an Intrinsic Property of Physical Objects 216
9.4.5 We Can Ascribe the Property of Being a Computer to Any Object 217
9.4.6 Everything Is a Computer 218
9.5 Patrick Hayes: Computers as Magic Paper 220
9.6 Gualtiero Piccinini: Computers as Digital String Manipulators 223
9.6.1 Definition P1 224
9.6.2 Definition P2 225
9.7 What Else Might Be a Computer? 226
9.7.1 Is a Brain a Computer? 226
9.7.2 Is the Universe a Computer? 228
9.8 Conclusion 232
9.9 Questions for the Reader 233
<b>Part III The Church-Turing Computability Thesis 237</b>
<b>10 Procedures 239</b>
10.1 Introduction 239
10.2 The Church-Turing Computability Thesis 240
10.3 What Is a Procedure? 243
10.4 Carol Cleland: Some Effective Procedures Are Not Turing Machines 244
10.5 Beth Preston: Recipes, Algorithms, and Specifications 249
10.6 Summary 251
10.7 Questions for the Reader 252
<b>11 Hypercomputation 253</b>
11.1 Introduction 253
11.2 Generic Computation 255
11.3 Non-Euclidean Geometries and "Non-Turing Computations" 255
11.4 Hypercomputation 256
11.5 "Newer Physics" Hypercomputers 257
11.6 Analog Recurrent Neural Networks 258
11.7 Objections to Hypercomputation 258
11.8 Interactive Computation 259
11.8.1 "Internal" vs. "External" Inputs 259
11.8.2 Batch vs. Online Processing 259
11.8.3 Peter Wegner: Interaction Is Not Turing-Computable 260
11.8.4 Can Interaction Be Simulated by a Non-Interactive Turing Machine? 263
11.8.4.1 The Power of Interaction 263
11.8.4.2 Simulating a Halting Interaction Machine 263
11.8.4.3 Simulating a Non-Halting Interaction Machine 265
11.9 Oracle Computation 266
11.10 Trial-and-Error Computation 270
11.10.1 Introduction 270
11.10.2 Does "Intelligence" Require Trial-and-Error Machines? 273
11.10.3 Inductive Inference 276
11.11 Summary 276
11.12 Questions for the Reader 278
<b>Part IV Computer Programs 281</b>
<b>12 Software and Hardware 283</b>
12.1 The Nature of Computer Programs 283
12.2 Programs and Algorithms 284
12.3 Software, Programs, and Hardware 285
12.3.1 Etymology of 'Software' 285
12.3.2 Software and Music 286
12.3.3 The Dual Nature of Programs 286
12.3.4 Copyright vs. Patent 287
12.4 Moor: Software Is Changeable 290
12.4.1 Levels of Understanding 290
12.4.2 Programs Are Relative to Computers 290
12.4.3 Instructions 291
12.4.4 "Following Instructions." 292
12.4.5 Moor's Definitions of 'Software' and 'Hardware.' 293
12.5 Suber: Software Is Pattern 294
12.6 Colburn: Software Is a Concrete Abstraction 297
12.7 Summary 299
12.8 Questions for the Reader 299
<b>13 Implementation 301</b>
13.1 Introduction 301
13.1.1 Implementation vs. Abstraction 302
13.1.2 Implementations as Role Players 303
13.1.3 Abstract Data Types 303
13.1.4 The Structure of Implementation 304
13.2 Implementation as Semantic Interpretation 305
13.2.1 What Kind of Relation Is Implementation? 305
13.2.2 Semantic Interpretation 306
13.2.2.1 Formal Systems 307
13.2.2.2 Syntax 307
13.2.2.3 Semantic Interpretation 308
13.2.3 Two Modes of Understanding 310
13.3 Chalmers's Theory of Implementation 313
13.3.1 Introduction 313
13.3.2 An Analysis of Chalmers's Theory 313
13.3.3 Rescorla's Analysis of Chalmers's Theory 317
<b>14 Computer Programs as Scientific Theories 321</b>
14.1 Introduction 321
14.2 Simulations 322
14.2.1 Simulation vs. Emulation 322
14.2.2 Simulation vs. Imitation 323
14.2.3 Models 323
14.2.4 Theories 324
14.3 Computer Programs Are Theories 325
14.3.1 Introduction 325
14.3.2 Simon and Newell's Argument from Analogies 327
14.3.3 Simon's Argument from Prediction 329
14.3.4 Daubert vs. Merrell-Dow 330
14.4 Computer Programs Aren't Theories 331
14.4.1 Moor's Objections 331
14.4.2 Thagard's Objections 333
<b>15 Computer Programs as Mathematical Objects 336</b>
15.1 Introduction 336
15.1.1 Bugs and Intended Behavior 336
15.1.2 Proofs and Programs 337
15.2 Theorem Verification 340
15.2.1 Theorems and Proofs 340
15.2.2 Programs and Proofs 341
15.2.3 Programs, Proofs, and Formal Systems 343
15.3 Program Verification 344
15.3.1 Introduction and Some History 344
15.3.2 Program Verification by Pre- and Post-Conditions 345
15.3.3 The Value of Program Verification 346
15.4 The Fetzer Controversy 347
15.4.1 Fetzer's Argument against Program Verification 347
15.4.2 The Controversy 350
15.4.3 Barwise's Attempt at Mediation 351
15.5 The Program-Verification Debate: Summary 352
15.6 Program Verification, Models, and the World 354
15.6.1 "Being Correct" vs. "Doing What's Intended" 354
15.6.2 Models: Putting the World into Computers 354
<b>16 Programs and the World 360</b>
16.1 Introduction 360
16.2 Internal vs. External Behavior: Some Examples 361
16.3 Two Views of Computation 364
16.4 Inputs, Turing Machines, and Outputs 365
16.4.1 Introduction 365
16.4.2 The Turing Machine Tape as Input-Output Device 365
16.4.3 Are Inputs Needed? 366
16.4.4 Are Outputs Needed? 367
16.4.5 When Are Inputs and Outputs Needed? 367
16.4.6 Must Inputs and Outputs Be Interpreted Alike? 368
16.4.7 Linking the Tape to the External World 370
16.5 Are Programs Teleological? 370
16.6 Algorithms Do Need a Purpose 371
16.7 Algorithms Don't Need a Purpose 373
16.8 Algorithms and Goals 375
16.9 Computing with Symbols or with Their Meanings 377
16.10 Syntactic, Internal, and Indigenous Semantics 380
16.10.1 Syntax vs. Semantics 380
16.10.2 Syntactic Semantics 380
16.10.3 Syntactic Semantics and Procedural Abstraction 382
16.10.4 Internalization 383
16.11 Content and Computation 384
16.11.1 Introduction 384
16.11.2 Symbols: Marks vs. Meanings 385
16.11.3 Shagrir's "Master Argument" 388
16.12 Summary 390
16.13 Questions for the Reader 391
<b>Part V Computer Ethics and Artificial Intelligence 393</b>
<b>17 Computer Ethics I: Should We Trust Computers? 395</b>
17.1 Introduction 395
17.2 Decisions and Computers 395
17.3 Are Computer Decisions Rational? 397
17.4 Should Computers Make Decisions for Us? 398
17.5 Should Computers Make Decisions with Us? 399
17.6 Should We Trust Decisions Computers Make? 400
17.6.1 The Bias Problem 400
17.6.2 The Black-Box Problem 401
17.7 Are There Decisions Computers Must Make for Us? 403
17.8 Are There Decisions Computers Shouldn't Make? 404
17.9 Questions for the Reader 405
<b>18 Philosophy of Artificial Intelligence 407</b>
18.1 Introduction 407
18.2 What Is AI? 407
18.2.1 Definitions and Goals of AI 407
18.2.2 Artificial Intelligence as Computational Cognition 408
18.3 The Turing Test 409
18.3.1 How Computers Can Think 409
18.3.2 The Imitation Game 410
18.3.3 Thinking vs. "Thinking" 412
18.4 Digression: The "Lovelace Objection" 415
18.5 Digression: Turing on Intelligent Machinery 417
18.6 The Chinese Room Argument 418
18.7 The Argument from Biology 420
18.7.1 Causal Powers 420
18.7.2 The Implementation Counterargument 421
18.8 The Argument from Semantics 422
18.8.1 The Premises 422
18.8.2 Which Premise Is at Fault? 423
18.8.3 Semiotics 424
18.8.4 Points of View 426
18.8.5 A Recursive Theory of Understanding 429
18.9 Leibniz's Mill and Turing's "Strange Inversion" 430
18.10 A Better Way 435
18.11 Questions for Discussion 436
<b>19 Computer Ethics II: Should We Build Artificial Intelligences? 438</b>
19.1 Introduction 438
19.2 Is AI Possible in Principle? 439
19.3 What Is a Person? 440
19.4 Rights 442
19.5 Responsibilities 443
19.6 Personal AIs and Morality 445
19.7 Are We Personal AIs? 445
19.8 Questions for the Reader 446
<b>Part VI Closing Remarks 449</b>
<b>20 Computer Science: A Personal View 451</b>
20.1 Introduction 451
20.2 Computer Science and Elephants 452
20.3 Five Central Questions of CS 454
20.3.1 Computability 454
20.3.2 Efficient Computability 456
20.3.3 Practical Computability 457
20.3.4 Physical Computability 458
20.3.5 Ethical Computability 458
20.4 Wing's Five Questions 459
20.5 Conclusion 460
Bibliography 461
Index 495
