Philosophy of Computer Science

William J. Rapaport is CSE Eminent Professor Emeritus in the Department of Computer Science and Engineering and an affiliated faculty member emeritus in the Departments of Philosophy and of Linguistics at the University at Buffalo, The State University of New York. He is a recipient of the Barwise Prize of the American Philosophical Association, the Covey Award of the International Association for Computing and Philosophy, and the SUNY Chancellor’s Award for Excellence in Teaching.

• List of Figures xviPreface xviiiAbout the Companion Website xxPart I Philosophy and Computer Science 11 An Introduction to the Philosophy of Computer Science 31.1 What This Book Is About 31.2 What This Book Is Not About 52 Philosophy: A Personal View 72.1 Introduction 72.2 A Definition of ‘Philosophy’ 82.3 What Is Truth? 92.3.1 Correspondence Theories of Truth 102.3.2 Coherence Theories of Truth 102.3.3 Correspondence vs. Coherence 102.4 Searching for the Truth 132.4.1 Searching vs. Finding 132.4.2 Asking “Why?” 142.4.3 Can There Be Progress in Philosophy? 152.4.4 Skepticism 162.5 What Is “Rational”? 172.5.1 Logical Rationality 172.5.2 Scientific Rationality 202.5.3 Computational Rationality 212.5.4 Is It Always Rational to Be Rational? 212.6 Philosophy as a Personal Search 222.7 Philosophies of Anything and Everything 232.8 Philosophy and Computer Science 252.9 Appendix: Argument Analysis and Evaluation 252.9.1 Introduction 252.9.2 A Question-Answer Game 262.9.3 Missing Premises 272.9.4 When Is an Argument a “Good” Argument? 302.9.5 Examples of Good and Bad Arguments 342.9.6 Summary 35Part II Computer Science, Computers, and Computation 373 What Is Computer Science? 393.1 Introduction 393.2 Naming the Discipline 393.3 Why Ask What CS Is? 403.4 What Does It Mean to Ask What Something Is? 423.4.1 Determining Boundaries 423.4.2 Extensional and Intensional Definition 453.5 CS as the Science of Computers 473.5.1 Objection: Computers Are Not Natural 483.5.2 Objection: Computers Are Tools, Not Phenomena 493.5.3 Digression: The Once-upon-a-Time Science of Microscopy 513.5.4 Objection: CS Is Just a Branch of … 523.5.5 Objection: What about Algorithms? 523.6 CS Studies Algorithms 533.6.1 Only Algorithms? 533.6.2 Or Computers, Too? 553.7 Physical Computers vs. Abstract Algorithms 563.8 CS Studies Information 573.9 CS as a Mathematical Science 583.10 CS as a Natural Science of Procedures 613.11 CS as an Empirical Study 633.12 CS as Engineering 643.13 Science xor Engineering? 663.14 CS as “Both” 663.15 CS as “More” 683.15.1 CS as a New Kind of Science 683.15.2 CS as a New Kind of Engineering 703.16 CS as “Neither” 713.16.1 CS as Art 713.16.2 CS as the Study of Complexity 713.16.3 CS as the Philosophy(!) of Procedures 723.16.4 CS as Computational Thinking 723.16.5 CS as AI 733.16.6 Is CS Magic? 743.17 Summary 763.18 Questions for the Reader 774 Science 784.1 Introduction 784.2 Science and Non-Science 794.3 Science as Systematic Study 804.4 The Goals of Science 814.4.1 Description 814.4.2 Explanation 824.4.3 Prediction 824.5 Instrumentalism vs. Realism 834.6 Scientific Theories 854.7 “The” Scientific Method 864.8 Falsifiability 884.8.1 Science as Conjectures and Refutations 884.8.2 The Logic of Falsifiability 894.8.3 Problems with Falsifiability 904.9 Scientific Revolutions 904.10 Other Alternatives 914.11 CS and Science 914.11.1 Is CS a Science? 914.11.2 What Kind of Science Might CS Be? 924.12 Questions to Think About 935 Engineering 955.1 Defining ‘Engineering’ 955.2 Engineering as Science 975.3 A Brief History of Engineering 985.4 Conceptions of Engineering 995.5 What Engineers Do 1005.5.1 Engineering as Design 1005.5.2 Engineering as Building 1005.6 The Engineering Method 1015.7 Software Engineering 1025.8 CS and Engineering 1045.9 Questions to Think About 1056 Computers: A Brief History 1076.1 Introduction 1076.2 Would You Like to Be a Computer? 1086.3 Two Histories of Computers 1096.4 The Engineering History 1096.4.1 Ancient Greece 1096.4.2 Seventeenth Century Calculating Machines 1106.4.3 Babbage’s Machines 1106.4.4 Electronic Computers 1116.4.5 Modern Computers 1126.5 The Scientific History 1136.6 The Histories Converge 1166.7 What Is a Computer? 1166.7.1 An Engineering Answer 1166.7.2 A Scientific Answer 1177 Algorithms and Computability 1197.1 Introduction 1197.2 Functions and Computation 1207.2.1 Mathematical Functions 1207.2.2 Functions Described Extensionally 1217.2.3 Functions Described Intensionally 1237.2.4 Function “Machines” 1257.2.5 Computable Functions 1267.3 ‘Algorithm’ Made Precise 1287.3.1 Ancient Algorithms 1287.3.2 “Effectiveness” 1287.3.3 Three Attempts at Precision 1297.4 Five Great Insights of CS 1347.4.1 Insight 1: Representation 1347.4.2 Insight 2: Processing 1357.4.3 Insight 3: Structure 1367.4.3.1 Structured Programming (I) 1367.4.3.2 Digression – Recursive Definitions 1377.4.3.3 Structured Programming (II) 1387.4.4 Insight 4: The Church-Turing Computability Thesis 1397.4.5 Insight 5: Implementation 1417.5 Structured Programming 1427.5.1 Basic Programs 1427.5.2 Program Constructors 1437.5.3 Classification of Structured Programs 1447.6 Recursive Functions 1447.6.1 A Recursive Definition of Natural Numbers 1447.6.2 Recursive Definitions of Recursive Functions 1457.6.3 Classification of Recursive Functions 1497.7 Non-Computable Functions 1507.7.1 The Halting Problem 1507.7.2 Proof Sketch that H Is Not Computable 1537.8 Summary 1557.9 Questions for the Reader 1558 Turing’s Analysis of Computation 1578.1 Introduction 1578.2 Slow and Active Reading 1588.3 Title: “The Entscheidungsproblem” 1588.4 Paragraph 1 1598.4.1 “ ‘Computable’ Numbers” 1598.4.2 “Written By a Machine” 1608.5 Paragraph 2 1608.5.1 “Naturally Regarded as Computable” 1608.5.2 “Definable Numbers” 1618.6 Section 1, Paragraph 1: “Computing Machines” 1618.7 Section 9: “The Extent of the Computable Numbers” 1628.7.1 Turing’s Computability Thesis 1628.7.2 “Writing Symbols on Paper” 1638.7.3 States of Mind 1668.7.4 Operations 1678.7.5 Another “Simple Operation” 1698.7.6 “Immediate Recognisability” 1698.7.7 Summary of Operations 1708.7.8 “States of Mind” 1708.7.9 Turing Machines, Turing’s Thesis, and AI 1728.8 “Computing Machines” 1748.8.1 “Man” and “Machine” 1758.8.2 Closure Clause: Turing’s Thesis 1788.9 Section 2: “Definitions” 1788.9.1 “Automatic Machines” 1788.9.2 “Choice Machines” 1798.9.3 “Computing Machines” 1798.9.4 “Complete Configurations” 1808.9.5 “Circular and Circle-Free Machines” 1818.9.6 “Circular” Machines 1828.9.7 “Computable Sequences and Numbers” 1838.10 Section 3: “Examples of Computing Machines” 1848.10.1 Example I 1848.10.2 Example II, Paragraph 1 1898.10.3 Example II, Paragraph 2 1928.11 Section 4: “Abbreviated Tables” 1958.12 Section 5: “Enumeration of Computable Sequences” 1968.13 Section 6: “The Universal Computing Machine” 2018.14 The Rest of Turing’s Paper 2039 Computers: A Philosophical Perspective 2049.1 What Is a Computer? 2049.2 Informal Definitions 2069.2.1 Reference-Book Definitions 2069.2.2 John von Neumann’s Definition 2069.2.3 Arthur Samuel’s Definition 2079.2.4 Martin Davis’s Characterization 2089.2.5 Summary 2089.3 Computers, Turing Machines, and Universal Turing Machines 2109.3.1 Computers as Turing Machines 2109.3.2 Stored Program vs. Programmable 2119.4 John Searle’s “Pancomputationalism”: Everything Is a Computer 2129.4.1 Searle’s Argument 2129.4.2 Computers Are Described in Terms of 0s and 1s 2139.4.3 Being a Computer Is a Syntactic Property 2149.4.4 Being a Computer Is Not an Intrinsic Property of Physical Objects 2169.4.5 We Can Ascribe the Property of Being a Computer to Any Object 2179.4.6 Everything Is a Computer 2189.5 Patrick Hayes: Computers as Magic Paper 2209.6 Gualtiero Piccinini: Computers as Digital String Manipulators 2239.6.1 Definition P1 2249.6.2 Definition P2 2259.7 What Else Might Be a Computer? 2269.7.1 Is a Brain a Computer? 2269.7.2 Is the Universe a Computer? 2289.8 Conclusion 2329.9 Questions for the Reader 233Part III The Church-Turing Computability Thesis 23710 Procedures 23910.1 Introduction 23910.2 The Church-Turing Computability Thesis 24010.3 What Is a Procedure? 24310.4 Carol Cleland: Some Effective Procedures Are Not Turing Machines 24410.5 Beth Preston: Recipes, Algorithms, and Specifications 24910.6 Summary 25110.7 Questions for the Reader 25211 Hypercomputation 25311.1 Introduction 25311.2 Generic Computation 25511.3 Non-Euclidean Geometries and “Non-Turing Computations” 25511.4 Hypercomputation 25611.5 “Newer Physics” Hypercomputers 25711.6 Analog Recurrent Neural Networks 25811.7 Objections to Hypercomputation 25811.8 Interactive Computation 25911.8.1 “Internal” vs. “External” Inputs 25911.8.2 Batch vs. Online Processing 25911.8.3 Peter Wegner: Interaction Is Not Turing-Computable 26011.8.4 Can Interaction Be Simulated by a Non-Interactive Turing Machine? 26311.8.4.1 The Power of Interaction 26311.8.4.2 Simulating a Halting Interaction Machine 26311.8.4.3 Simulating a Non-Halting Interaction Machine 26511.9 Oracle Computation 26611.10 Trial-and-Error Computation 27011.10.1 Introduction 27011.10.2 Does “Intelligence” Require Trial-and-Error Machines? 27311.10.3 Inductive Inference 27611.11 Summary 27611.12 Questions for the Reader 278Part IV Computer Programs 28112 Software and Hardware 28312.1 The Nature of Computer Programs 28312.2 Programs and Algorithms 28412.3 Software, Programs, and Hardware 28512.3.1 Etymology of ‘Software’ 28512.3.2 Software and Music 28612.3.3 The Dual Nature of Programs 28612.3.4 Copyright vs. Patent 28712.4 Moor: Software Is Changeable 29012.4.1 Levels of Understanding 29012.4.2 Programs Are Relative to Computers 29012.4.3 Instructions 29112.4.4 “Following Instructions.” 29212.4.5 Moor’s Definitions of ‘Software’ and ‘Hardware.’ 29312.5 Suber: Software Is Pattern 29412.6 Colburn: Software Is a Concrete Abstraction 29712.7 Summary 29912.8 Questions for the Reader 29913 Implementation 30113.1 Introduction 30113.1.1 Implementation vs. Abstraction 30213.1.2 Implementations as Role Players 30313.1.3 Abstract Data Types 30313.1.4 The Structure of Implementation 30413.2 Implementation as Semantic Interpretation 30513.2.1 What Kind of Relation Is Implementation? 30513.2.2 Semantic Interpretation 30613.2.2.1 Formal Systems 30713.2.2.2 Syntax 30713.2.2.3 Semantic Interpretation 30813.2.3 Two Modes of Understanding 31013.3 Chalmers’s Theory of Implementation 31313.3.1 Introduction 31313.3.2 An Analysis of Chalmers’s Theory 31313.3.3 Rescorla’s Analysis of Chalmers’s Theory 31714 Computer Programs as Scientific Theories 32114.1 Introduction 32114.2 Simulations 32214.2.1 Simulation vs. Emulation 32214.2.2 Simulation vs. Imitation 32314.2.3 Models 32314.2.4 Theories 32414.3 Computer Programs Are Theories 32514.3.1 Introduction 32514.3.2 Simon and Newell’s Argument from Analogies 32714.3.3 Simon’s Argument from Prediction 32914.3.4 Daubert vs. Merrell-Dow 33014.4 Computer Programs Aren’t Theories 33114.4.1 Moor’s Objections 33114.4.2 Thagard’s Objections 33315 Computer Programs as Mathematical Objects 33615.1 Introduction 33615.1.1 Bugs and Intended Behavior 33615.1.2 Proofs and Programs 33715.2 Theorem Verification 34015.2.1 Theorems and Proofs 34015.2.2 Programs and Proofs 34115.2.3 Programs, Proofs, and Formal Systems 34315.3 Program Verification 34415.3.1 Introduction and Some History 34415.3.2 Program Verification by Pre- and Post-Conditions 34515.3.3 The Value of Program Verification 34615.4 The Fetzer Controversy 34715.4.1 Fetzer’s Argument against Program Verification 34715.4.2 The Controversy 35015.4.3 Barwise’s Attempt at Mediation 35115.5 The Program-Verification Debate: Summary 35215.6 Program Verification, Models, and the World 35415.6.1 “Being Correct” vs. “Doing What’s Intended” 35415.6.2 Models: Putting the World into Computers 35416 Programs and the World 36016.1 Introduction 36016.2 Internal vs. External Behavior: Some Examples 36116.3 Two Views of Computation 36416.4 Inputs, Turing Machines, and Outputs 36516.4.1 Introduction 36516.4.2 The Turing Machine Tape as Input-Output Device 36516.4.3 Are Inputs Needed? 36616.4.4 Are Outputs Needed? 36716.4.5 When Are Inputs and Outputs Needed? 36716.4.6 Must Inputs and Outputs Be Interpreted Alike? 36816.4.7 Linking the Tape to the External World 37016.5 Are Programs Teleological? 37016.6 Algorithms Do Need a Purpose 37116.7 Algorithms Don’t Need a Purpose 37316.8 Algorithms and Goals 37516.9 Computing with Symbols or with Their Meanings 37716.10 Syntactic, Internal, and Indigenous Semantics 38016.10.1 Syntax vs. Semantics 38016.10.2 Syntactic Semantics 38016.10.3 Syntactic Semantics and Procedural Abstraction 38216.10.4 Internalization 38316.11 Content and Computation 38416.11.1 Introduction 38416.11.2 Symbols: Marks vs. Meanings 38516.11.3 Shagrir’s “Master Argument” 38816.12 Summary 39016.13 Questions for the Reader 391Part V Computer Ethics and Artificial Intelligence 39317 Computer Ethics I: Should We Trust Computers? 39517.1 Introduction 39517.2 Decisions and Computers 39517.3 Are Computer Decisions Rational? 39717.4 Should Computers Make Decisions for Us? 39817.5 Should Computers Make Decisions with Us? 39917.6 Should We Trust Decisions Computers Make? 40017.6.1 The Bias Problem 40017.6.2 The Black-Box Problem 40117.7 Are There Decisions Computers Must Make for Us? 40317.8 Are There Decisions Computers Shouldn’t Make? 40417.9 Questions for the Reader 40518 Philosophy of Artificial Intelligence 40718.1 Introduction 40718.2 What Is AI? 40718.2.1 Definitions and Goals of AI 40718.2.2 Artificial Intelligence as Computational Cognition 40818.3 The Turing Test 40918.3.1 How Computers Can Think 40918.3.2 The Imitation Game 41018.3.3 Thinking vs. “Thinking” 41218.4 Digression: The “Lovelace Objection” 41518.5 Digression: Turing on Intelligent Machinery 41718.6 The Chinese Room Argument 41818.7 The Argument from Biology 42018.7.1 Causal Powers 42018.7.2 The Implementation Counterargument 42118.8 The Argument from Semantics 42218.8.1 The Premises 42218.8.2 Which Premise Is at Fault? 42318.8.3 Semiotics 42418.8.4 Points of View 42618.8.5 A Recursive Theory of Understanding 42918.9 Leibniz’s Mill and Turing’s “Strange Inversion” 43018.10 A Better Way 43518.11 Questions for Discussion 43619 Computer Ethics II: Should We Build Artificial Intelligences? 43819.1 Introduction 43819.2 Is AI Possible in Principle? 43919.3 What Is a Person? 44019.4 Rights 44219.5 Responsibilities 44319.6 Personal AIs and Morality 44519.7 Are We Personal AIs? 44519.8 Questions for the Reader 446Part VI Closing Remarks 44920 Computer Science: A Personal View 45120.1 Introduction 45120.2 Computer Science and Elephants 45220.3 Five Central Questions of CS 45420.3.1 Computability 45420.3.2 Efficient Computability 45620.3.3 Practical Computability 45720.3.4 Physical Computability 45820.3.5 Ethical Computability 45820.4 Wing’s Five Questions 45920.5 Conclusion 460Bibliography 461Index 495