Citations of:
Program verification: the very idea
Communications of the Acm 31 (9):1048--1063 (1988)
Add citations
You must login to add citations.
|
|
Taken at face value, a programming language is defined by a formal grammar. But, clearly, there is more to it. By themselves, the naked strings of the language do not determine when a program is correct relative to some specification. For this, the constructs of the language must be given some semantic content. Moreover, to be employed to generate physical computations, a programming language must have a physical implementation. How are we to conceptualize this complex package? Ontologically, what kind of (...) |
|
How can we be certain that software is reliable? Is there any method that can verify the correctness of software for all cases of interest? Computer scientists and software engineers have informally assumed that there is no fully general solution to the verification problem. In this paper, we survey approaches to the problem of software verification and offer a new proof for why there can be no general solution. |
|
How can we be certain that software is reliable? Is there any method that can verify the correctness of software for all cases of interest? Computer scientists and software engineers have informally assumed that there is no fully general solution to the verification problem. In this paper, we survey approaches to the problem of software verification and offer a new proof for why there can be no general solution. |
|
Engineering is often said to be ‘scientific’, but the nature of knowledge in engineering is different to science. Engineering has a different ontological basis—its theories address different entities and are judged by different criteria. In this paper I use Popper’s three worlds ontological framework to propose a model of engineering theories, and provide an abstract logical view of engineering theories analogous to the deductive-nomological view of scientific theories. These models frame three key elements from definitions of engineering: requirements, designs of (...) |
|
A response to a recent critique by Cem Bozşahin of the theory of syntactic semantics as it applies to Helen Keller, and some applications of the theory to the philosophy of computer science. |
|
One might poetically muse that computers have the essence both of logic and machines. Through the case of the history of Separation Logic, we explore how this assertion is more than idle poetry. Separation Logic works because it merges the software engineer’s conceptual model of a program’s manipulation of computer memory with the logical model that interprets what sentences in the logic are true, and because it has a proof theory which aids in the crucial problem of scaling the reasoning (...) No categories |
|
This article presents the evolution of philosophical and methodological considerations concerning empiricism in computer/computing science. In this study, we trace the most important current events in the history of reflection on computing. The forerunners of Artificial Intelligence H.A. Simon and A. Newell in their paper Computer Science As Empirical Inquiry started these considerations. Later the concept of empirical computer science was developed by S.S. Shapiro, P. Wegner, A.H. Eden and P.J. Denning. They showed various empirical aspects of computing. This led (...) No categories |
|
The issue of proper functioning of operative computing and the utility of program verification, both in general and of specific methods, has been discussed a lot. In many of those discussions, attempts have been made to take mathematics as a model of knowledge and certitude achieving, and accordingly infer about the suitable ways to handle computing. I shortly review three approaches to the subject, and then take a stance by considering social factors which affect the epistemic status of both mathematics (...) |
|
The notion of specification plays a key role in the developing science of computing. It is typically considered to be the keystone in the software development process. However, there is no single, generally agreed meaning of specification that bears close scrutiny. Instead there is a variety of different, although partially interlocking and overlapping interpretations of the term.We catalogue this varietal profusion and attempt to lay bare both the sources and consequences of each major alternative. We attempt to present the full (...) |
|
A proof of ‘correctness’ for a mathematical algorithm cannot be relevant to executions of a program based on that algorithm because both the algorithm and the proof are based on assumptions that do not hold for computations carried out by real-world computers. Thus, proving the ‘correctness’ of an algorithm cannot establish the trustworthiness of programs based on that algorithm. Despite the (deceptive) sameness of the notations used to represent them, the transformation of an algorithm into an executable program is a (...) |
|
Like other mathematically intensive sciences, economics is becoming increasingly computerized. Despite the extent of the computation, however, there is very little true simulation. Simple computation is a form of theory articulation, whereas true simulation is analogous to an experimental procedure. Successful computation is faithful to an underlying mathematical model, whereas successful simulation directly mimics a process or a system. The computer is seen as a legitimate tool in economics only when traditional analytical solutions cannot be derived, i.e., only as a (...) |
|
|
|
|
|
On the basis of an earlier contribution to the philosophy of computer science by Amnon Eden, this essay discusses to what extent Eden’s ‘paradigms’ of computer science can be transferred or applied to software engineering. This discussion implies an analysis of how software engineering and computer science are related to each other. The essay concludes that software engineering can neither be fully subsumed by computer science, nor vice versa. Consequently, also the philosophies of computer science and software engineering—though related to (...) |
|
The formal sciences - mathematical as opposed to natural sciences, such as operations research, statistics, theoretical computer science, systems engineering - appear to have achieved mathematically provable knowledge directly about the real world. It is argued that this appearance is correct. |
|
A debate over the theoretical capabilities of formal methods in computer science has raged for more than two years now. The function of this paper is to summarize the key elements of this debate and to respond to important criticisms others have advanced by placing these issues within a broader context of philosophical considerations about the nature of hardware and of software and about the kinds of knowledge that we have the capacity to acquire concerning their performance. |
|
The essays included in the special issue dedicated to the philosophy of computer science examine new philosophical questions that arise from reflection upon conceptual issues in computer science and the insights such an enquiry provides into ongoing philosophical debates. |
|
The birth, growth, stabilization and subsequent understanding of a new field of practical and theoretical enquiry is always a conceptual process including several typologies of events, phenomena an... |
|
In this paper I attempt to cast the current program verification debate within a more general perspective on the methodologies and goals of computer science. I show, first, how any method involved in demonstrating the correctness of a physically executing computer program, whether by testing or formal verification, involves reasoning that is defeasible in nature. Then, through a delineation of the senses in which programs can be run as tests, I show that the activities of testing and formal verification do (...) |
|
We characterize abstraction in computer science by first comparing the fundamental nature of computer science with that of its cousin mathematics. We consider their primary products, use of formalism, and abstraction objectives, and find that the two disciplines are sharply distinguished. Mathematics, being primarily concerned with developing inference structures, has information neglect as its abstraction objective. Computer science, being primarily concerned with developing interaction patterns, has information hiding as its abstraction objective. We show that abstraction through information hiding is a (...) |
|
In the technical literature of computer science, the concept of an effective procedure is closely associated with the notion of an instruction that precisely specifies an action. Turing machine instructions are held up as providing paragons of instructions that "precisely describe" or "well define" the actions they prescribe. Numerical algorithms and computer programs are judged effective just insofar as they are thought to be translatable into Turing machine programs. Nontechnical procedures (e.g., recipes, methods) are summarily dismissed as ineffective on the (...) |
|
Fetzer famously claims that program verification is not even a theoretical possibility, and offers a certain argument for this far-reaching claim. Unfortunately for Fetzer, and like-minded thinkers, this position-argument pair, while based on a seminal insight that program verification, despite its Platonic proof-theoretic airs, is plagued by the inevitable unreliability of messy, real-world causation, is demonstrably self-refuting. As I soon show, Fetzer is like the person who claims: ‘My sole claim is that every claim expressed by an English sentence and (...) |
|
The form of nominalism known as 'mathematical fictionalism' is examined and found wanting, mainly on grounds that go back to an early antinominalist work of Rudolf Carnap that has unfortunately not been paid sufficient attention by more recent writers. |
|
Model checking, a prominent formal method used to predict and explain the behaviour of software and hardware systems, is examined on the basis of reflective work in the philosophy of science concerning the ontology of scientific theories and model-based reasoning. The empirical theories of computational systems that model checking techniques enable one to build are identified, in the light of the semantic conception of scientific theories, with families of models that are interconnected by simulation relations. And the mappings between these (...) |
|
There are many branches of philosophy called “the philosophy of X,” where X = disciplines ranging from history to physics. The philosophy of artificial intelligence has a long history, and there are many courses and texts with that title. Surprisingly, the philosophy of computer science is not nearly as well-developed. This article proposes topics that might constitute the philosophy of computer science and describes a course covering those topics, along with suggested readings and assignments. |
|
An early version of the work on mathematics as the science of structure that appeared later as An Aristotelian Realist Philosophy of Mathematics (2014). |
|
This book addresses key conceptual issues relating to the modern scientific and engineering use of computer simulations. It analyses a broad set of questions, from the nature of computer simulations to their epistemological power, including the many scientific, social and ethics implications of using computer simulations. The book is written in an easily accessible narrative, one that weaves together philosophical questions and scientific technicalities. It will thus appeal equally to all academic scientists, engineers, and researchers in industry interested in questions (...) |
|
Aristotelian, or non-Platonist, realism holds that mathematics is a science of the real world, just as much as biology or sociology are. Where biology studies living things and sociology studies human social relations, mathematics studies the quantitative or structural aspects of things, such as ratios, or patterns, or complexity, or numerosity, or symmetry. Let us start with an example, as Aristotelians always prefer, an example that introduces the essential themes of the Aristotelian view of mathematics. A typical mathematical truth is (...) |
|
The proper treatment of computationalism, as the thesis that cognition is computable, is presented and defended. Some arguments of James H. Fetzer against computationalism are examined and found wanting, and his positive theory of minds as semiotic systems is shown to be consistent with computationalism. An objection is raised to an argument of Selmer Bringsjord against one strand of computationalism, namely, that Turing-Test± passing artifacts are persons, it is argued that, whether or not this objection holds, such artifacts will inevitably (...) |
|
|
|
The classical theory of computation does not represent an adequate model of reality for simulation in the social sciences. The aim of this paper is to construct a methodological perspective that is able to conciliate the formal and empirical logic of program verification in computer science, with the interpretative and multiparadigmatic logic of the social sciences. We attempt to evaluate whether social simulation implies an additional perspective about the way one can understand the concepts of program and computation. We demonstrate (...) |
|
This paper is concerned with the construction of theories of software systems yielding adequate predictions of their target systems’ computations. It is first argued that mathematical theories of programs are not able to provide predictions that are consistent with observed executions. Empirical theories of software systems are here introduced semantically, in terms of a hierarchy of computational models that are supplied by formal methods and testing techniques in computer science. Both deductive top-down and inductive bottom-up approaches in the discovery of (...) |
|
|
|
In this paper, I review the objections against the claim that brains are computers, or, to be precise, information-processing mechanisms. By showing that practically all the popular objections are either based on uncharitable interpretation of the claim, or simply wrong, I argue that the claim is likely to be true, relevant to contemporary cognitive (neuro)science, and non-trivial. |
|
A philosophical appraisal of historical positions on the nature of thought, mentality, and intelligence, this survey begins with the views of Descartes, Turing, and Newell and Simon, but includes the work of Haugeland, Fodor, Searle, and other major scholars. The underlying issues concern distinctions between syntax, semantics, and pragmatics, where physical computers seem to be best viewed as mark-manipulating or syntax-processing mechanisms. Alternative accounts have been advanced of what it takes to be a thinking thing, including being Turing machines, symbol (...) |
|
My dissertation focuses on mathematical explanation found in proofs looked at from a historical point of view, while stressing the importance of mathematical practices. Current philosophical theories on explanatory proofs emphasize the structure and content of proofs without any regard to external factors that influence a proof’s explanatory power. As a result, the major philosophical views have been shown to be inadequate in capturing general aspects of explanation. I argue that, in addition to form and content, a proof’s explanatory power (...) No categories |
|
Una imagen muy generalizada a la hora de entender el software de computador es la que lo representa como una “caja negra”: no importa realmente saber qué partes lo componen internamente, sino qué resultados se obtienen de él según ciertos valores de entrada. Al hacer esto, muchos problemas filosóficos son ocultados, negados o simplemente mal entendidos. Este artículo discute tres unidades de análisis del software de computador, esto es, las especificaciones, los algoritmos y los procesos computacionales. El objetivo central es (...) |