One recursively enumerable real α dominates another one β if there are nondecreasing recursive sequences of rational numbers (a[n] : n ∈ ω) approximating α and (b[n] : n ∈ ω) approximating β and a positive constant C such that for all n, C(α − a[n]) ≥ (β − b[n]). See [R. M. Solovay, Draft of a Paper (or Series of Papers) on Chaitin’s Work, manuscript, IBM Thomas J. Watson Research Center, Yorktown Heights, NY, 1974, p. 215] and [G. J. (...) Chaitin, IBM J. Res. Develop., 21 (1977), pp. 350–359]. We show that every recursively enumerable random real dominates all other recursively enumerable reals. We conclude that the recursively enumerable random reals are exactly the Ω-numbers [G. J. Chaitin, IBM J. Res. Develop., 21 (1977), pp. 350–359]. Second, we show that the sets in a universal Martin-Lof test for randomness have random measure, and every recursively enumerable random number is the sum of the measures represented in a universal Martin-Lof test. (shrink)

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)

This paper offers an account of what it is for a physical system to be a computing mechanism—a system that performs computations. A computing mechanism is a mechanism whose function is to generate output strings from input strings and (possibly) internal states, in accordance with a general rule that applies to all relevant strings and depends on the input strings and (possibly) internal states for its application. This account is motivated by reasons endogenous to the philosophy of (...) class='Hi'>computing, namely, doing justice to the practices of computer scientists and computability theorists. It is also an application of recent literature on mechanisms, because it assimilates computational explanation to mechanistic explanation. The account can be used to individuate computing mechanisms and the functions they compute and to taxonomize computing mechanisms based on their computing power. (shrink)

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. (shrink)

The central paradigm of arti?cial intelligence is rapidly shifting toward biological models for both robotic devices and systems performing such critical tasks as network management, vehicle navigation, and process control. Here we use a recent mathematical analysis of the necessary conditions for consciousness in humans to explore likely failure modes inherent to a broad class of biologically inspired computing machines. Analogs to developmental psychopathology, in which regulatory mechanisms for consciousness fail progressively and subtly understress, and toinattentional blindness, where a (...) narrow 'syntactic band pass' de?ned by the rate distortion manifold of conscious attention results in pathological ?xation, seem inevitable. Similar problems are likely to confront other possible architectures, although their mathematical description may be far less straightforward. Computing devices constructed on biological paradigms will inevitably lack the elaborate, but poorly understood, system of control mechanisms which has evolved over the last few hundred million years to stabilize consciousness in higher animals. This will make such machines prone to insidious degradation, and, ultimately, catastrophic failure. (shrink)

The aim of this paper is to begin developing a version of Gualtiero Piccinini’s mechanistic account of computation that does not need to appeal to any notion of proper (or teleological) functions. The motivation for doing so is a general concern about the role played by proper functions in Piccinini’s account, which will be evaluated in the first part of the paper. I will then propose a potential alternative approach, where computing mechanisms are understood in terms of Carl Craver’s (...) perspectival account of mechanistic functions. According to this approach, the mechanistic function of ‘performing a computation’ can only be attributed relative to an explanatory perspective, but such attributions are nonetheless constrained by the underlying physical structure of the system in question, thus avoiding unlimited pancomputationalism. If successful, this approach would carry with it fewer controversial assumptions than Piccinini’s original account, which requires a robust understanding of proper functions. Insofar as there are outstanding concerns about the status of proper functions, this approach would therefore be more generally acceptable. (shrink)

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 (...) class='Hi'>computing. This led to a view of the science of computing - the science of general scope. Some interesting contemporary ways towards a generalized perspective on computations were also shown. (shrink)

I propose to consider the question, "Can machines think?" This should begin with definitions of the meaning of the terms "machine" and "think." The definitions might be framed so as to reflect so far as possible the normal use of the words, but this attitude is dangerous, If the meaning of the words "machine" and "think" are to be found by examining how they are commonly used it is difficult to escape the conclusion that the meaning and the answer to (...) the question, "Can machines think?" is to be sought in a statistical survey such as a Gallup poll. But this is absurd. Instead of attempting such a definition I shall replace the question by another, which is closely related to it and is expressed in relatively unambiguous words. The new form of the problem can be described in terms of a game which we call the 'imitation game." It is played with three people, a man (A), a woman (B), and an interrogator (C) who may be of either sex. The interrogator stays in a room apart front the other two. The object of the game for the interrogator is to determine which of the other two is the man and which is the woman. He knows them by labels X and Y, and at the end of the game he says either "X is A and Y is B" or "X is B and Y is A." The interrogator is allowed to put questions to A and B. We now ask the question, "What will happen when a machine takes the part of A in this game?" Will the interrogator decide wrongly as often when the game is played like this as he does when the game is played between a man and a woman? These questions replace our original, "Can machines think?". (shrink)

We show that the number of types of sequences of tuples of a fixed length can be calculated from the number of 1-types and the length of the sequences. Specifically, if κ≤λ, then sup ‖M‖=λ|Sκ|=|)κ. We show that this holds for any abstract elementary class with λ-amalgamation. No such calculation is possible for nonalgebraic types. However, we introduce a subclass of nonalgebraic types for which the same upper bound holds.

Computing and information, and their philosophy in the broad sense, play a most important scientific, technological and conceptual role in our world. This book collects together, for the first time, the views and experiences of some of the visionary pioneers and most influential thinkers in such a fundamental area of our intellectual development.

This dissertation examines aspects of the interplay between computing and scientific practice. The appropriate foundational framework for such an endeavour is rather real computability than the classical computability theory. This is so because physical sciences, engineering, and applied mathematics mostly employ functions defined in continuous domains. But, contrary to the case of computation over natural numbers, there is no universally accepted framework for real computation; rather, there are two incompatible approaches --computable analysis and BSS model--, both claiming to formalise (...) algorithmic computation and to offer foundations for scientific computing. -/- The dissertation consists of three parts. In the first part, we examine what notion of 'algorithmic computation' underlies each approach and how it is respectively formalised. It is argued that the very existence of the two rival frameworks indicates that 'algorithm' is not one unique concept in mathematics, but it is used in more than one way. We test this hypothesis for consistency with mathematical practice as well as with key foundational works that aim to define the term. As a result, new connections between certain subfields of mathematics and computer science are drawn, and a distinction between 'algorithms' and 'effective procedures' is proposed. -/- In the second part, we focus on the second goal of the two rival approaches to real computation; namely, to provide foundations for scientific computing. We examine both frameworks in detail, what idealisations they employ, and how they relate to floating-point arithmetic systems used in real computers. We explore limitations and advantages of both frameworks, and answer questions about which one is preferable for computational modelling and which one for addressing general computability issues. -/- In the third part, analog computing and its relation to analogue (physical) modelling in science are investigated. Based on some paradigmatic cases of the former, a certain view about the nature of computation is defended, and the indispensable role of representation in it is emphasized and accounted for. We also propose a novel account of the distinction between analog and digital computation and, based on it, we compare analog computational modelling to physical modelling. It is concluded that the two practices, despite their apparent similarities, are orthogonal. (shrink)

Affective computing research has advanced emotion recognition systems using facial expressions, voices, gaits, and physiological signals, yet these methods are often impractical. This study integrates mouse cursor motion analysis into affective computing and investigates the idea that movements of the computer cursor can provide information about emotion of the computer user. We extracted 16–26 trajectory features during a choice-reaching task and examined the link between emotion and cursor motions. Participants were induced for positive or negative emotions by music, (...) film clips, or emotional pictures, and they indicated their emotions with questionnaires. Our 10-fold cross-validation analysis shows that statistical models formed from “known” participants could predict nearly 10%–20% of the variance of positive affect and attentiveness ratings of “unknown” participants, suggesting that cursor movement patterns such as the area under curve and direction change help infer emotions of computer users. (shrink)

In his 1950 paper “Computing Machinery and Intelligence,” Alan Turing proposed that we can determine whether a machine thinks by considering whether it can win at a simple imitation game. A neutral questioner communicates with two different systems – one a machine and a human being – without knowing which is which. If after some reasonable amount of time the machine is able to fool the questioner into identifying it as the human, the machine wins the game, and we (...) should conclude that it thinks. This imitation game, now known as the Turing Test, has been much discussed by philosophers of mind, and for more than half a century now there has been considerable debate about whether it is an adequate test for thinking. But what has not been much discussed are the sexed presuppositions underlying the test. Too often forgotten in the philosophical discussion is the fact that Turing’s imitation game is modeled on an imitation game in which a neutral questioner communicates with two different humans – one a man and one a woman – without knowing which is which. In this original imitation game, the man wins the game if he is able to fool the questioner into identifying him as the woman. In this paper, I explore the implications of this set-up. As I argue, the fact that the Turing test was modeled on a man/woman imitation game seems to have led us astray in various ways in our attempt to conduct an effective investigation and assessment of computer intelligence. (shrink)

influence. One of the principal characteristics that distinguishes Cognitive Science from more traditional studies of cognition within Psychology, is the extent to which it has been influenced by both the ideas and the techniques of computing. It may come as a surprise to the outsider, then, to discover that there is no unanimity within the discipline on either (a) the nature (and in some cases the desireabilty) of the influence and (b) what computing is –- or at least (...) on its. (shrink)

This paper continues the power ordering approach to verisimilitude. We define a parameterized verisimilar ordering of theories in the finite propositional case, both semantically and syntactically. The syntactic definition leads to an algorithm for computing verisimilitude. Since the power ordering approach to verisimilitude can be translated into a standard notion of belief revision, the algorithm thereby also allows the computation of membership of a belief-revised theory.

This dissertation examines aspects of the interplay between computing and scientific practice. The appropriate foundational framework for such an endeavour is rather real computability than the classical computability theory. This is so because physical sciences, engineering, and applied mathematics mostly employ functions defined in continuous domains. But, contrary to the case of computation over natural numbers, there is no universally accepted framework for real computation; rather, there are two incompatible approaches --computable analysis and BSS model--, both claiming to formalise (...) algorithmic computation and to offer foundations for scientific computing. The dissertation consists of three parts. In the first part, we examine what notion of 'algorithmic computation' underlies each approach and how it is respectively formalised. It is argued that the very existence of the two rival frameworks indicates that 'algorithm' is not one unique concept in mathematics, but it is used in more than one way. We test this hypothesis for consistency with mathematical practice as well as with key foundational works that aim to define the term. As a result, new connections between certain subfields of mathematics and computer science are drawn, and a distinction between 'algorithms' and 'effective procedures' is proposed. In the second part, we focus on the second goal of the two rival approaches to real computation; namely, to provide foundations for scientific computing. We examine both frameworks in detail, what idealisations they employ, and how they relate to floating-point arithmetic systems used in real computers. We explore limitations and advantages of both frameworks, and answer questions about which one is preferable for computational modelling and which one for addressing general computability issues. In the third part, analog computing and its relation to analogue (physical) modelling in science are investigated. Based on some paradigmatic cases of the former, a certain view about the nature of computation is defended, and the indispensable role of representation in it is emphasized and accounted for. We also propose a novel account of the distinction between analog and digital computation and, based on it, we compare analog computational modelling to physical modelling. It is concluded that the two practices, despite their apparent similarities, are orthogonal. (shrink)

Query processing in ground definite deductive is known to correspond precisely to a linear programming problem. However, the “groundedness” requirement is a huge drawback to using linear programming techniques for logic program computations because the ground version of a logic program can be very large when compared to the original program. Furthermore, when we move from propositional logic programs to first-order logic programs, this effectively means that functions symbols may not occur in clauses. In this paper, we develop a theory (...) of “instantiate- by-need” that performs instantiations only when needed. We prove that this method is sound and complete when computing answer substitutions for non-ground logic programs including those containing function symbols. More importantly, when taken in conjunction with Colmerauer's result that unification can be viewed as linear programming, this means that resolution with unification can be completely replaced by linear programming as an operational paradigm. Additionally, our tree construction method is not rigidly tied to the linear programming paradigm-we will show that given any method M that can compute the set of atomic logical consequences of a propositional logic program, our method can use M to compute , the set of all atoms that are consequences of a first-order logic program. (shrink)

In [8], the third author defined a reducibility$\le _w^{\rm{*}}$that lets us compare the computing power of structures of any cardinality. In [6], the first two authors showed that the ordered field of reals${\cal R}$lies strictly above certain related structures. In the present paper, we show that$\left \equiv _w^{\rm{*}}{\cal R}$. More generally, for the weak-looking structure${\cal R}$ℚconsisting of the real numbers with just the ordering and constants naming the rationals, allo-minimal expansions of${\cal R}$ℚare equivalent to${\cal R}$. Using this, we show (...) that for any analytic functionf,$\left \equiv _w^{\rm{*}}{\cal R}$. $is noto-minimal.). (shrink)

This paper investigates ontological dimensions of the blockchain by asking what kind of socio-technical object bitcoin is. It discusses both blockchain's political qualities and the political forms enabled by its emergence. It first observes recent approaches to the ontology of money and the political qualities of the ledgers used by the current fractional reserve banking model. It then directs the same questions at blockchain technology. The paper discusses an ontology proposed by Ole Bjerg and argues in favour of a mixed-ontology (...) approach to blockchains. It then questions the political qualities of the distributed ledger as a digital object and highlights the apparent absence of authority figures in the model. Finally, it argues that the political ontology of the blockchain can be framed as the displacement of authority from institutional actors into instrumental control of trust, in a dynamically distributed environment. (shrink)

Computing as a science is the study of computers, both the hardware and their programs, and all that goes with them (Newell and Simon 1976). The philosophy of computer science is concerned with problems of a philosophical kind raised by the discipline's goals, fundamental ideas, techniques or methods, and findings. It parallels other parts of philosophy ‐ for example, the philosophy of economics or linguistics or biology ‐ in primarily considering problems raised by one discipline, rather than issues raised (...) by a group of disciplines, as does the philosophy of science in general. (shrink)

Affect plays an important role in the consumer decision-making process and there is growing interest in the development of new technologies and computational approaches that can interpret and recognize the affects of consumers, with benefits for marketing described in relation to both academia and industry. From an interdisciplinary perspective, this paper aims to review past studies focused on electroencephalography (EEG)-based affective computing (AC) in marketing, which provides a promising avenue for studying the mechanisms underlying affective states and developing recognition (...) computational models to predict the psychological responses of customers. This review offers an introduction to EEG technology and an overview of EEG-based AC; provides a snapshot of the current state of the literature. It briefly presents the themes, challenges, and trends in studies of affect evaluation, recognition, and classification; and further proposes potential guidelines for researchers and marketers. (shrink)

The mechanistic approach in philosophy of science contributes to our understanding of experimental design. Applying the mechanistic approach to experimentation in computing is beneficial for two reasons. It connects the methodology of experimentation in computing with the methodology of experimentation in established sciences, thereby strengthening the scientific reputability of computing and the quality of experimental design therein. Furthermore, it pinpoints the idiosyncrasies of experimentation in computing: computing deals closely with both natural and engineered mechanisms. Better (...) understanding of the idiosyncrasies, which manifest in terms of a nonstandard role for experimentation, are interesting both for computer scientists and for philosophers of science. Computer scientists can think more clearly about their experimental choices. The role of experimentation elucidated by computer science merits further study from philosophers of science generally, as it highlights a role for experimentation hitherto unrecognized by philosophers: demonstration that activities exist. (shrink)

Any attempt to conceptualize, categorize and constraint foundational issues in a living science, such as Computing, is bound to show its limitations and leave a number of open issues. Taking stock with some critical reviews of Primiero (On the foundations of computing, Oxford University Press, Oxford, 2019) published in this Journal, I overview potential new problems to be investigated by a foundational analysis of the science of computing.

Artificial Intelligence (AI) is a technology widely used to support human decision-making. Current areas of application include financial services, engineering, and management. A number of attempts to introduce AI decision support systems into areas which more obviously include moral judgement have been made. These include systems that give advice on patient care, on social benefit entitlement, and even ethical advice for medical professionals. Responding to these developments raises a complex set of moral questions. This paper proposes a clearer replacement question (...) to them. The replacement question asks under what circumstances, if any, people would accept a moral judgement made by some sort of machine. Since, it is argued, the answer to this replacement question is positive, urgent practical moral problems are raised. (shrink)