This book constitutes the strictly refereed post-workshop proceedings of the 11th International Workshop on Computer Science Logic, CSL '97, held as the 1997 Annual Conference of the European Association on Computer Science Logic, EACSL, in Aarhus, Denmark, in August 1997. The volume presents 26 revised full papers selected after two rounds of refereeing from initially 92 submissions; also included are four invited papers. The book addresses all current aspects of computer science logics and its (...) applications and thus presents the state of the art in the area. (shrink)

Colburn (computer science, U. of Minnesota-Duluth) has a doctorate in philosophy and an advanced degree in computer science; he's worked as a philosophy professor, a computer programmer, and a research scientist in artificial intelligence. Here he discusses the philosophical foundations of artificial intelligence; the new encounter of science and philosophy (logic, models of the mind and of reasoning, epistemology); and the philosophy of computer science (touching on math, abstraction, software, and ontology).

The prelims comprise: Introduction Computer Science and Mathematics The Formal Verification Debate Abstraction in Computer Science Conclusion.

This volume presents the proceedings of the workshop CSL '91 (Computer Science Logic) held at the University of Berne, Switzerland, October 7-11, 1991. This was the fifth in a series of annual workshops on computer sciencelogic (the first four are recorded in LNCS volumes 329, 385, 440, and 533). The volume contains 33 invited and selected papers on a variety of logical topics in computer science, including abstract datatypes, bounded theories, complexity results, cut elimination, denotational (...) semantics, infinitary queries, Kleene algebra with recursion, minimal proofs, normal forms in infinite-valued logic, ordinal processes, persistent Petri nets, plausibility logic, program synthesis systems, quantifier hierarchies, semantics of modularization, stable logic, term rewriting systems, termination of logic programs, transitive closure logic, variants of resolution, and many others. (shrink)

This paper aims to connect Stiegler’s reflections on theoretical computer science with his practical propositions for the design of digital technologies. Indeed, Stiegler’s theory of exosomatization implies a new conception of artificial intelligence, which is not based on an analogical paradigm (which compares organisms and machines, as in cybernetics, or which compares thought and computing, as in cognitivism) but on an organological paradigm, which studies the co-evolution of living organisms (individuals), artificial organs (tools), and social organizations (institutions). Such (...) a perspective does not compare human capacities to machine performances but studies the way in which the evolution of material and technical supports affects and transforms psychological, cognitive or noetic faculties (intuition, memory, understanding, imagination, sensibility, reason, etc.), as well as the constitution of different kinds of knowledge. This new theoretical paradigm implies a new ‘design’ for digital technologies, which considers their social role and their impact on psychological, cognitive or noetic faculties. (shrink)

This reader contains the extended abstracts of the seminars organised for the “Computer Science and IT with/for Biology” Seminar Series, held at the Faculty of Computer Science, Free University of Bozen-Bolzano, from October to December 2005. Slides of the presentations are available online at: www.inf.unibz.it/krdb/biology.

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.

Computational methods such as computer simulations, Monte Carlo methods, and agent-based modeling have become the dominant techniques in many areas of science. Extending Ourselves contains the first systematic philosophical account of these new methods, and how they require a different approach to scientific method. Paul Humphreys draws a parallel between the ways in which such computational methods have enhanced our abilities to mathematically model the world, and the more familiar ways in which scientific instruments have expanded our access (...) to the empirical world. This expansion forms the basis for a new kind of empiricism, better suited to the needs of science than the older anthropocentric forms of empiricism. Human abilities are no longer the ultimate standard of epistemological correctness.Humphreys also includes arguments for the primacy of properties rather than objects, the need to consider technological constraints when appraising scientific methods, and a detailed account of how the path from computational template to scientific application is constructed. This last feature allows us to hold a form of selective realism in which anti-realist arguments based on formal reconstructions of theories can be avoided. One important consequence of the rise of computational methods is that the traditional organization of the sciences is being replaced by an organization founded on computational templates.Extending Ourselves will be of interest to philosophers of science, epistemologists, and to anyone interested in the role played by computers in modern science. (shrink)

What is computer-science about? CS is obviously the science of computers. But what exactly are computers? We know that there are physical computers, and, perhaps, also abstract computers. Let us limit the discussion here to physical entities and ask: What are physical computers? What does it mean for a physical entity to be a computer? The answer, it seems, is that physical computers are physical dynamical systems that implement formal entities such as Turing-machines. I do not (...) think that this answer is false. But it invites another, and troubling, question: What distinguishes computers from other physical dynamical systems? The difficulty is that, on the one hand, every physical system im-plements abstract formal entities such as sets of differential equations, while on the other hand we certainly do not want to count every dynamical system as a computer. After all, if CS is somehow distinctive, then there must be a difference between computers and other systems such as solar systems, stomachs, and carburetors. But what is the difference? (shrink)

Recently, information retrieval is shown to be a science by mapping information retrieval scientific study to scientific study abstracted from physics. The exercise was rather tedious and lengthy. Instead of dealing with the nitty gritty, this paper looks at the insights into how computer science can be made into a science by using that methodology. That is by mapping computer science scientific study to the scientific study abstracted from physics. To show the mapping between (...) computer science and physics, we need to define what is engineering science which computer science belongs to. Some principles and assumptions of engineering science theory are presented. To show computer science is a science, we presented two approaches. Approach 1 considers computer science as simulation of human behaviour similar to the goal of artificial intelligence. Approach 2 is closely related to the actual activities in computer science, and this approach considers computer science based on the theory of computation. Finally, we answer some of the common outstanding issues about computer science to convince our reader that computer science is a science. (shrink)

The subject of this study is the problem of the failure of attempts by the scientific community to come to a common understanding of what exactly information can be as something encoded into material structures and moved along with them. At the same time, the following aspects of this problem are considered in detail: what is the immediate cause of the information problem; what are the objective and subjective prerequisites for its appearance; why the unresolved nature of this problem does (...) not interfere with the creation and development of communication systems, control and other "smart" devices; is there any general guideline for finding solutions to such problems, and what is it; what role did the philosophy of information play in turning the problem of information from a private scientific problem into a problem of the ideological level. The main results of the conducted research are as follows: the immediate cause of the information problem has been identified and a comprehensively substantiated solution to this problem has been given; it has been revealed that the incompleteness of the materialistic theory of cognition has become a fertile ground for the appearance of this problem; the circumstances that prevented its completion have been identified; the natural mechanism of control and cognition has been revealed, as a result of which the materialistic theory of cognition has been further developed the source of the ideal in the material world is revealed; it is shown that the mechanistic idea of information coding made the concept of information incompatible with the presence of any objective content; it is revealed what is actually hidden behind the words about information coding and its measurement; the nature of signals and signs is revealed; a kind of bias of the philosophy of information and a general error is revealed all known concepts of information. (shrink)

I critically review Raymond Turner’s Computational Artifacts – Towards a Philosophy of Computer Science by placing beside his position a rather different one, according to which computer science is a branch of, and is therefore subsumed by, immaterial formal logic.

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.

Linear Logic is a branch of proof theory which provides refined tools for the study of the computational aspects of proofs. These tools include a duality-based categorical semantics, an intrinsic graphical representation of proofs, the introduction of well-behaved non-commutative logical connectives, and the concepts of polarity and focalisation. These various aspects are illustrated here through introductory tutorials as well as more specialised contributions, with a particular emphasis on applications to computer science: denotational semantics, lambda-calculus, logic programming and concurrency (...) theory. The volume is rounded-off by two invited contributions on new topics rooted in recent developments of linear logic. The book derives from a summer school that was the climax of the EU Training and Mobility of Researchers project 'Linear Logic in Computer Science'. It is an excellent introduction to some of the most active research topics in the area. (shrink)

Analogicity in computer science is understood in two, not mutually exclusive ways: 1) with regard to the continuity feature (of data or computations), 2) with regard to the analogousness feature (i.e. similarity between certain natural processes and computations). Continuous computations are the subject of three methodological questions considered in the paper: 1a) to what extent do their theoretical models go beyond the model of the universal Turing machine (defining digital computations), 1b) is their computational power greater than that (...) of the universal Turing machine, 1c) under what conditions are continuous computations realizable in practice? The analogue-analogical computations lead to two other issues: 2a) in what sense and to what extent their accuracy depends on the adequacy of certain theories of empirical sciences, 2b) are there analogue-analogical computations in nature that are also continuous? The above issues are an important element of the philosophical discussion on the limitations of contemporary computer science. (shrink)

The related fields of fractal image encoding and fractal image analysis have blossomed in recent years. This book, originating from a NATO Advanced Study Institute held in 1995, presents work by leading researchers. It is developing the subjects at an introductory level, but it also has some recent and exciting results in both fields. The book contains a thorough discussion of fractal image compression and decompression, including both continuous and discrete formulations, vector space and hierarchical methods, and algorithmic optimizations. The (...) book also discusses multifractal approaches to image analysis, segmentation, and recognition, including medical applications. (shrink)

The article deals with Russian scientific classifications (GRNTI, VAK) of computer science in comparison with Western scien­tific classifications Fields of Science and Technology (FOS) and Universal Decimal Classification (UDS). The author analyzes the basics and principles of these classifications, identifies their strong and weak points as well as their influence on the devel­opment of computer sciences. She also provides some recom­mendations on adjustments of Russian scientific classifications aiming to make them more flexible and adaptive to the (...) faster scientific and technological development and interdisciplinary cooperation. (shrink)

In this paper I hope to show that the idea of teaching philosophy through teaching computer science is a project worth pursuing. In the first section I will sketch a variety of ways in which philosophy and computer science might interact. Then I will give a brief rationale for teaching philosophy through teaching computer science. Then I will introduce three philosophical issues (among others) that have pedagogically useful analogues in computer science: (i) (...) external world skepticism, (ii) numerical vs. qualitative identity, and (iii) the existence of God. (shrink)

This book looks at the ways in which conditionals, an integral part of philosophy and logic, can be of practical use in computer programming. It analyzes the different types of conditionals, including their applications and potential problems. Other topics include defeasible logics, the Ramsey test, and a unified view of consequence relation and belief revision. Its implications will be of interest to researchers in logic, philosophy, and computer science, particularly artificial intelligence.

This volume presents the proceedings of the Computer Science Logic Workshop CSL '92, held in Pisa, Italy, in September/October 1992. CSL '92 was the sixth of the series and the first one held as Annual Conference of the European Association for Computer Science Logic (EACSL). Full versions of the workshop contributions were collected after their presentation and reviewed. On the basis of 58 reviews, 26 papers were selected for publication, and appear here in revised final form. (...) Topics covered in the volume include: Turing machines, linear logic, logic of proofs, optimization problems, lambda calculus, fixpoint logic, NP-completeness, resolution, transition system semantics, higher order partial functions, evolving algebras, functional logic programming, inductive definability, semantics of C, classes for a functional language, NP-optimization problems, theory of types and names, sconing and relators, 3-satisfiability, Kleene's slash, negation-complete logic programs, polynomial-time oracle machines, and monadic second-order properties. (shrink)

Epistemic logic has grown from its philosophical beginnings to find diverse applications in computer science, and as a means of reasoning about the knowledge and belief of agents. This book provides a broad introduction to the subject, along with many exercises and their solutions. The authors begin by presenting the necessary apparatus from mathematics and logic, including Kripke semantics and the well-known modal logics K, T, S4 and S5. Then they turn to applications in the context of distributed (...) systems and artificial intelligence. These include the notions of common knowledge, distributed knowledge, explicit and implicit belief, the interplays between knowledge and time, and knowledge and action, as well as a graded (or numerical) variant of the epistemic operators. The authors also discuss extensively the problem of logical omniscience. They cover Halpern & Moses' theory of honest formulas, and they make a digression into the realm of nonmonotonic reasoning and preferential entailment. They discuss Moore's autoepistemic logic, together with Levesque's related logic of "all I know". Furthermore, they show how one can base default and counterfactual reasoning on epistemic logic. Graduate students in philosophy or in computer science, especially those with an interest in AI, will find this book useful. (shrink)

The integration of computer science, biology, and engineering has resulted in the emergence of rapidly growing interdisciplinary fields such as bioinformatics, bioengineering, DNA computing, and systems and synthetic biology. Ideas derived from computer science and engineering can provide innovative solutions to biological problems and advance research in new directions. Although interdisciplinary research has become increasingly prevalent in recent years, the scientists contributing to these efforts largely remain specialists in their original disciplines and are not fully capable (...) of covering the many facets of multidisciplinary problems, which impedes the development of truly integrated solutions. It would be .. (shrink)

Computational philosophy is the use of mechanized computational techniques to unearth philosophical insights that are either difficult or impossible to find using traditional philosophical methods. Computational metaphysics is computational philosophy with a focus on metaphysics. In this paper, we (a) develop results in modal metaphysics whose discovery was computer assisted, and (b) conclude that these results work not only to the obvious benefit of philosophy but also, less obviously, to the benefit of computer science, since the new (...) computational techniques that led to these results may be more broadly applicable within computer science. The paper includes a description of our background methodology and how it evolved, and a discussion of our new results. (shrink)

The Annual Conference of the European Association for Computer Science Logic, CSL 2002, was held in the Old College of the University of Edinburgh on 22–25 September 2002. The conference series started as a programme of Int- national Workshops on Computer Science Logic, and then in its sixth meeting became the Annual Conference of the EACSL. This conference was the sixteenth meeting and eleventh EACSL conference; it was organized by the Laboratory for Foundations of Computer (...) Science at the University of Edinburgh. The CSL 2002 Programme Committee considered 111 submissions from 28 countries during a two week electronic discussion; each paper was refereed by at least three reviewers. The Committee selected 37 papers for presentation at the conference and publication in these proceedings. The Programme Committee invited lectures from Susumu Hayashi, Frank Neven, and Damian Niwinski; ́ the papers provided by the invited speakers appear at the front of this volume. In addition to the main conference, two tutorials – ‘Introduction to Mu- Calculi’ and ‘Parametrized Complexity’ – were given on the previous day. (shrink)

An excessive preoccupation with formalism is impeding the development of computer science. Form- content confusion is discussed relative to three areas: theory of computation, programming languages, and education.

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 primary factor in computer science progress and success through an examination of the ubiquitous role of information hiding in programming languages, operating systems, network architecture, and design patterns. (shrink)

The process of constructing mathematical models is examined and a case made that the construction process is an integral part of the justification for the model. The role of heuristics in testing and modifying models is described and some consequences for scientific methodology are drawn out. Three different ways of constructing the same model are detailed to demonstrate the claims made here.

An understanding of logic is essential to computer science. This book provides a highly accessible account of the logical basis required for reasoning about computer programs and applying logic in fields like artificial intelligence. The text contains extended examples, algorithms, and programs written in Standard ML and Prolog. No prior knowledge of either language is required. The book contains a clear account of classical first-order logic, one of the basic tools for program verification, as well as an (...) introductory survey of modal and temporal logics and possible world semantics. An introduction to intuitionistic logic as a basis for an important style of program specification is also featured in the book. (shrink)

Alfred Tarski’s influence on computer science was indirect but significant in a number of directions and was in certain respects fundamental. Here surveyed is Tarski’s work on the decision procedure for algebra and geometry, the method of elimination of quantifiers, the semantics of formal languages, model-theoretic preservation theorems, and algebraic logic; various connections of each with computer science are taken up.

The simulation hypothesis has recently excited renewed interest, especially in the physics and philosophy communities. However, the hypothesis specifically concerns {computers} that simulate physical universes, which means that to properly investigate it we need to couple computer science theory with physics. Here I do this by exploiting the physical Church-Turing thesis. This allows me to introduce a preliminary investigation of some of the computer science theoretic aspects of the simulation hypothesis. In particular, building on Kleene's second (...) recursion theorem, I prove that it is mathematically possible for us to be in a simulation that is being run on a computer \textit{by us}. In such a case, there would be two identical instances of us; the question of which of those is ``really us'' is meaningless. I also show how Rice's theorem provides some interesting impossibility results concerning simulation and self-simulation; briefly describe the philosophical implications of fully homomorphic encryption for (self-)simulation; briefly investigate the graphical structure of universes simulating universes simulating universes, among other issues. I end by describing some of the possible avenues for future research that this preliminary investigation reveals. (shrink)

The Interpolation Theorem, first formulated and proved by W. Craig fifty years ago for predicate logic, has been extended to many other logical frameworks and is being applied in several areas of computer science. We give a short overview, and focus on the theory of software systems and modules. An algebra of theories TA is presented, with a nonstandard interpretation of the existential quantifier ∃. In TA, the interpolation property of the underlying logic corresponds with the quantifier combination (...) property ∃Σ ∃П S ≡ ∃(Σ ∪ П) S. It is shown how the Modularization Theorem, the Factorization Lemma and the Normal Form Theorem for module expressions can be proved in TA. (shrink)

A useful logic in which to specify normative system behaviour, deontic logic has a broad spectrum of possible applications within the field: from legal expert systems to natural language processing, database integrity to electronic contracting and the specification of fault-tolerant software.

This paper contains a discussion of striking similarities between influential philosophical concepts of the past and the approaches currently employed in selected areas of computer science. In particular, works of the Pythagoreans, Plato, Abelard, Ash’arites, Malebranche and Berkeley are presented and contrasted with such computer science ideas as digital computers, object-oriented programming, the modelling of an object’s actions and causality in virtual environments, and 3D graphics rendering. The intention of this paper is to provoke the (...) class='Hi'>computer science community to go off the beaten path in order to find inspiration for the development of new approaches in software engineering. (shrink)

There is a widely extended image of computer software as some sort of ‘black box,’ where it does not matter how it internally works, but rather what sort of results are obtained given certain input values. By approaching computer software this way, many philosophical issues are hidden, neglected, or simply misunderstood. This article discusses three units of analysis of computer software, namely, specifications, algorithms, and computer processes. The aim is to understand the scientific and engineering practices (...) supporting each unit of analysis, as well as to analyze their methodology, ontology, and epistemology. (shrink)

Here we describe how writing exercises based on Value Analysis Design, an approach to the design and implementation of technological systems, can build skills in both philosophical reflection and philosophical writing. While not a replacement for long-form philosophical writing, these exercises are ways to help students develop both philosophical and writing skills. Not only do they do so without requiring the extensive feedback that is required for long-form writing, but they are also opportunities for STEM students and other non-philosophy majors (...) to acquire skills in ethical reflection, analysis, and communication. (shrink)

We examine the philosophical disputes among computer scientists concerning methodological, ontological, and epistemological questions: Is computer science a branch of mathematics, an engineering discipline, or a natural science? Should knowledge about the behaviour of programs proceed deductively or empirically? Are computer programs on a par with mathematical objects, with mere data, or with mental processes? We conclude that distinct positions taken in regard to these questions emanate from distinct sets of received beliefs or paradigms within (...) the discipline: – The rationalist paradigm, which was common among theoretical computer scientists, defines computer science as a branch of mathematics, treats programs on a par with mathematical objects, and seeks certain, a priori knowledge about their ‘correctness’ by means of deductive reasoning. – The technocratic paradigm, promulgated mainly by software engineers and has come to dominate much of the discipline, defines computer science as an engineering discipline, treats programs as mere data, and seeks probable, a posteriori knowledge about their reliability empirically using testing suites. – The scientific paradigm, prevalent in the branches of artificial intelligence, defines computer science as a natural (empirical) science, takes programs to be entities on a par with mental processes, and seeks a priori and a posteriori knowledge about them by combining formal deduction and scientific experimentation. We demonstrate evidence corroborating the tenets of the scientific paradigm, in particular the claim that program-processes are on a par with mental processes. We conclude with a discussion in the influence that the technocratic paradigm has been having over computer science. (shrink)

This festschrift volume is dedicated to Boris (Boaz) Trakhtenbrot on the occasion of his 85th birthday. For over half a century, Trakhtenbrot has been making seminal contributions to virtually all of the central areas of theoretical computer science. He is universally admired as a founding father and long-standing pillar of the discipline of computer science. On Friday, 28 April 2006, the School of Computer Science at Tel Aviv University held a “Computation Day Celebrating Boaz (...) (Boris) Trakhtenbrot's Eighty-Fifth Birthday”. As a follow-up to that event, his students and colleagues were asked to contribute to a volume in his honor and in recognition of his grand contributions to the field. The book opens with two historical overviews and a bibliography. These are followed by 33 thoroughly reviewed technical contributions. The broad range of topics covered include mathematical logic, logics for computer science, mathematics for computer science, automata and formal languages, asynchronous computation, semantics of programming languages, verification, and software engineering. This tapestry of subjects stands as testimony to the vast scope of Trakhtenbrot's achievements and the profound influence he has had on the field. (shrink)

Abstract: Laws of computer science are prescriptive in nature but can have descriptive analogs in the physical sciences. Here, we describe a law of conservation of information in network programming, and various laws of computational motion (invariants) for programming in general, along with their pedagogical utility. Invariants specify constraints on objects in abstract computational worlds, so we describe language and data abstraction employed by software developers and compare them to Floridi's concept of levels of abstraction. We also consider (...) Floridi's structural account of reality and its fit for describing abstract computational worlds. Being abstract, such worlds are products of programmers' creative imaginations, so any "laws" in these worlds are easily broken. The worlds of computational objects need laws in the form of self-prescribed invariants, but the suspension of these laws might be creative acts. Bending the rules of abstract reality facilitates algorithm design, as we demonstrate through the example of search trees. (shrink)

What do philosophy and computer science have in common? It turns out, quite a lot! In providing an introduction to computer science (using Python), Daniel Lim presents in this book key philosophical issues, ranging from external world skepticism to the existence of God to the problem of induction. These issues, and others, are introduced through the use of critical computational concepts, ranging from image manipulation to recursive programming to elementary machine learning techniques. In illuminating some of (...) the overlapping conceptual spaces of computer science and philosophy, Lim teaches readers fundamental programming skills and allows them to develop the critical thinking skills essential for examining some of the enduring questions of philosophy. (shrink)

Part I presents a model of interactive computation and a metric for expressiveness, Part II relates interactive models of computation to physics, and Part III considers empirical models from a philosophical perspective. Interaction machines, which extend Turing Machines to interaction, are shown in Part I to be more expressive than Turing Machines by a direct proof, by adapting Gödel's incompleteness result, and by observability metrics. Observation equivalence provides a tool for measuring expressiveness according to which interactive systems are more expressive (...) than algorithms. Refinement of function equivalence by observation of outer interactive behavior and inner computation steps is examined. The change of focus from algorithms specified by computable functions to interaction specified by observation equivalence captures the essence of empirical computer science. Part II relates interaction in models of computation to observation in the natural sciences. Explanatory power in physics is specified by the same observability metric as expressiveness in interactive systems. Realist models of inner structure are characterized by induction, abduction, and Occam's Razor. Interactive realism extends the hidden-variable model of Einstein to hidden interfaces that provide extra degrees of freedom to formulate hypotheses with testable predictions conforming with quantum theory. Greater expressiveness of collaborative computational observers (writers) than single observers implies that hidden-interface models are more expressive than hidden-variable models. By providing a common foundation for empirical computational and physical models we can use precise results about computational models to establish properties of physical models. Part III shows that the evolution in computing from algorithms to interaction parallels that in physics from rationalism to empiricism. Plato's cave metaphor is interactively extended from Platonic rationalism to empiricism. The Turing test is extended to TMs with hidden interfaces that express interactive thinking richer than the traditional Turing test. Interactive (nonmonotonic) extensions of logic such as the closed-world assumption suggest that interactiveness is incompatible with monotonic logical inference. Procedure call, atomicity of transactions, and taking a fixed point are techniques for closing open systems similar to "preparation" followed by "observation" of a physical system. Pragmatics is introduced as a framework for extending logical models with a fixed syntax and semantics to multiple-interface models that support collaboration among clients sharing common resources. (shrink)