Computing, today more than ever before, is a multi-faceted discipline which collates several methodologies, areas of interest, and approaches: mathematics, engineering, programming, and applications. Given its enormous impact on everyday life, it is essential that its debated origins are understood, and that its different foundations are explained. On the Foundations of Computing offers a comprehensive and critical overview of the birth and evolution of computing, and it presents some of the most important technical results and philosophical problems of the discipline, combining both historical and systematic analyses.
The debates this text surveys are among the latest and most urgent ones: the crisis of foundations in mathematics and the birth of the decision problem, the nature of algorithms, the debates on computational artefacts and malfunctioning, and the analysis of computational experiments. By covering these topics, On the Foundations of Computing provides a much-needed resource to contextualize these foundational issues.
For practitioners, researchers, and students alike, a historical and philosophical approach such as what this volume offers becomes essential to understand the past of the discipline and to figure out the challenges of its future.
Author(s): Giuseppe Primiero
Publisher: Oxford University Press
Year: 2020
Language: English
Pages: xx+296
Cover
On the Foundations of Computing
Copy Right
Preface
Acknowledgements
Contents
1 Introduction
Part I The Mathematical Foundation
2 A Fundamental Crisis
Summary
2.1 The Foundations of Mathematics Debated
2.2 Logical Roots
2.3 Logicism
2.4 Finitism
2.5 Intuitionism
Exercises
3 Computing and Deciding
Summary
3.1 Enumerability
3.2 Encoding
3.3 Diagonalization
3.4 The Decision Problem
Exercises
4 What is Computable?
Summary
4.1 Mathematical Induction
4.2 Primitive Recursion
4.3 Partial Recursion
4.4 Church’s Thesis
Exercises
5 Mechanical Computation
Summary
5.1 Turing Computability
5.2 The Universal Machine
5.3 The Halting Problem
5.4 Turing’s Thesis
Exercises
6 On the Nature of Algorithms
Summary
6.1 Fast Backwards
6.2 Intuitive Explanation
6.3 Algorithms as Specifications
6.4 Algorithms as Procedures
6.5 Algorithms as Abstract Machines
6.6 Equivalent Algorithms
Exercises
7 Computing as aMathematical Discipline
Summary
7.1 Proofs as Programs
7.2 Program Correctness
7.3 The Debate
7.4 Formal Computational Validity
Exercises
Part II The Engineering Foundation
8 The First Generation of Computers
Summary
8.1 Shannon’s Circuits
8.2 Early Memories
8.3 von Neumann Design
8.4 Universality and All-purposefulness
Exercises
9 The Laws of Evolution
Summary
9.1 Computing grows
9.2 New Memories
9.3 Miniaturization, Parallelism, and Compatibility
9.4 The First Law
9.5 Computational Growth
Exercises
10 Properties of Implemented Computations
Summary
10.1 Physical Computing
10.2 Functionality
10.3 Usability
10.4 Efficiency
10.5 Limits of the Church-Turing Thesis
Exercises
11 Specification and Implementation
Summary
11.1 The Debate on Implementation
11.2 Correct Implementations
11.3 Miscomputation
Exercises
12 Computing as anEngineering Discipline
Summary
12.1 Software Engineering
12.2 The Debate
12.3 Physical Computational Validity
Exercises
Part III The Experimental Foundation
13 Elements of Experimental Computing
Summary
13.1 Experimental Computer Science
13.2 On Computational Hypotheses
13.3 On Computational Experiments
Exercises
14 Models and Simulations
Summary
14.1 On Models
14.2 On Computer Simulations
14.3 Epistemic Role of Computer Simulations
Exercises
15 Formal Relations
Summary
15.1 Identity and Dependence
15.2 Isomorphism
15.3 Analogy and Similarity
15.4 Variants of Simulationism
Exercises
16 Computing as anExperimental Discipline
Summary
16.1 A Balanced Approach
16.2 Evaluation
16.3 Maximal Criteria: Robustness and Reliability
16.4 Minimal Criteria: Usability and Fitness
16.5 Experimental Computational Validity
Exercises
17 Conclusion
Bibliography
Index
