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 (...) scientific theories and computational systems in their scope are analyzed in terms of suitable specializations of the notions of model of experiment and model of data. Furthermore, the extensively mechanized character of model-based reasoning in model checking is highlighted by a comparison with proof procedures adopted by other formal methods in computer science. Finally, potential epistemic benefits flowing from the application of model checking in other areas of scientific inquiry are emphasized in the context of computer simulation studies of biological information processing. (shrink)

Some computational phenomena rely essentially on pragmatic considerations, and seem to undermine the independence of the specification from the implementation. These include software development, deviant uses, esoteric languages and recent data-driven applications. To account for them, the interaction between pragmatics, epistemology and ontology in computational artefacts seems essential, indicating the need to recover the role of the language metaphor. We propose a User Levels (ULs) structure as a pragmatic complement to the Levels of Abstraction (LoAs)-based structure defining the ontology and (...) epistemology of computational artefacts. ULs identify a flexible hierarchy in which users bear their own semantic and normative requirements, possibly competing with the logical specification. We formulate a notion of computational act intended in its pragmatic sense, alongside pragmatic versions of implementation and correctness. (shrink)

I articulate and defend a new theory of what it is for a physical system to implement an abstract computational model. According to my descriptivist theory, a physical system implements a computational model just in case the model accurately describes the system. Specifically, the system must reliably transit between computational states in accord with mechanical instructions encoded by the model. I contrast my theory with an influential approach to computational implementation espoused by Chalmers, Putnam, and others. I (...) deploy my theory to illuminate the relation between computation and representation. I also rebut arguments, propounded by Putnam and Searle, that computational implementation is trivial. (shrink)

The notion of computability is developed through the study of the behavior of a set of languages interpreted over the natural numbers which contain their own fully defined satisfaction predicate and whose only other vocabulary is limited to "0", individual variables, the successor function, the identity relation and operators for disjunction, conjunction, and existential quantification.

The chapters of this volume all have their own level of presentation. The topics have been chosen based on the active research interest associated with them. Since the interest in some topics is older than that in others, some presentations contain fundamental definitions and basic results while others relate very little of the elementary theory behind them and aim directly toward an exposition of advanced results. Presentations of the latter sort are in some cases restricted to a short survey (...) of recent results (due to the complexity of the methods and proofs themselves). Hence the variation in level of presentation from chapter to chapter only reflects the conceptual situation itself. One example of this is the collective efforts to develop an acceptable theory of computation on the real numbers. The last two decades has seen at least two new definitions of effective operations on the real numbers. (shrink)

In addition, this book contains tools that, in principle, can search a set of algorithms to see whether a problem is solvable, or more specifically, if it can be solved by an algorithm whose computations are efficient.

This paper was motivated by the following two questions which arise in the theory of complexity for computation over ordered rings in the now famous computational model introduced by Blum, Shub and Smale: 1. is the answer to the question P = ?NP the same in every real-closed field?2. if P ≠ NP for , does there exist a problem of which is NP but neither P nor NP-complete ?Some unclassical complexity classes arise naturally in the study of (...) these questions. They are still open, but we could obtain unconditional results of independent interest.Michaux introduced/const complexity classes in an effort to attack question . We show that , answering a question of his. Here A is the class of real problems which are algorithmic in bounded time. We also prove the stronger result: , where PAR stands for parallel polynomial time. In our terminology, we say that is A-saturated and PAR-saturated. We also prove, at the nonuniform level, the above results for every real-closed field. It is not known whether is P-saturated. In the case of the reals with addition and order we obtain P-saturation ). More generally, we show that an ordered -vector space is P-saturated at the nonuniform level ).We also study a stronger notion that we call P-stability. Blum, Cucker, Shub and Smale have shown that fields of characteristic 0 are P-stable. We show that the reals with addition and order are P-stable, but real-closed fields are not.Questions and and the/const complexity classes have some model theoretic flavor. This leads to the theory of complexity over “arbitrary” structures as introduced by Poizat. We give a summary of this theory with a special emphasis on the connections with model theory and we study/const complexity classes from this point of view. Note also that our proof of the PAR-saturation of shows that an o-minimal structure which admits quantifier elimination is A-saturated at the nonuniform level. (shrink)

Computable structures of Scott rank ${\omega_1^{CK}}$ are an important boundary case for structural complexity. While every countable structure is determined, up to isomorphism, by a sentence of ${\mathcal{L}_{\omega_1 \omega}}$ , this sentence may not be computable. We give examples, in several familiar classes of structures, of computable structures with Scott rank ${\omega_1^{CK}}$ whose computable infinitary theories are each ${\aleph_0}$ -categorical. General conditions are given, covering many known methods for constructing computable structures with Scott rank ${\omega_1^{CK}}$ , which guarantee that the (...) resulting structure is a model of an ${\aleph_0}$ -categorical computable infinitary theory. (shrink)

We show that the theory of the partial order of computably enumerable equivalence relations (ceers) under computable reduction is 1-equivalent to true arithmetic. We show the same result for the structure comprised of the dark ceers and the structure comprised of the light ceers. We also show the same for the structure of L-degrees in the dark, light, or complete structure. In each case, we show that there is an interpretable copy of (N, +, \times) .

The book provides the first full length exploration of fuzzy computability. It describes the notion of fuzziness and present the foundation of computability theory. It then presents the various approaches to fuzzy computability. This text provides a glimpse into the different approaches in this area, which is important for researchers in order to have a clear view of the field. It contains a detailed literature review and the author includes all proofs to make the presentation accessible. Ideas for future (...) research and explorations are also provided. Students and researchers in computer science and mathematics will benefit from this work. (shrink)

Under what conditions does a physical system implement or realize a computation? Structuralism about computational implementation, espoused by Chalmers and others, holds that a physical system realizes a computation just in case the system instantiates a pattern of causal organization isomorphic to the computation’s formal structure. I argue against structuralism through counter-examples drawn from computer science. On my opposing view, computational implementation sometimes requires instantiating semantic properties that outstrip any relevant pattern of causal organization. In developing my (...) argument, I defend anti-individualism about computational implementation: relations to the social environment sometimes help determine whether a physical system realizes a computation. 1 The Physical Realization Relation2 Semantics and Computational Implementation3 Conforming to Instructions4 Implementing a Computer Program4.1 The denotational semantics of Scheme4.2 Worries about intentionality4.3 Worries about the natural numbers5 Implementing a Machine Model6 Bounded Structuralism7 Triviality Arguments8 Anti-individualism about Computational Implementation. (shrink)

Following Marr (1982), any computational account of cognition must satisfy constraints at three explanatory levels: computational, algorithmic, and implementational. This paper focuses on the first two levels and argues that current theories of reasoning cannot provide explanations of everyday defeasible reasoning, at either level. At the algorithmic level, current theories are not computationally tractable: they do not “scale-up” to everyday defeasible inference. In addition, at the computational level, they cannot specify why people behave as they do both on laboratory reasoning (...) tasks and in everyday life (Anderson, 1990). In current theories, logic provides the computational-level theory, where such a theory is evident at all. But logic is not a descriptively adequate computational-level theory for many reasoning tasks. It is argued that better computational-level theories can be developed using a probabilistic framework. This approach is illustrated using Oaksford and Chater's (1994) probabilistic account of Wason's selection task. (shrink)

The state of computing science and, particularly, software engineering and knowledge engineering is generally considered immature. The best starting point for achieving a mature engineering discipline is a solid scientific theory, and the primary reason behind the immaturity in these fields is precisely that computing science still has no such agreed upon underlying theory. As theories in other fields of science do, this paper formally establishes the fundamental elements and postulates making up a first attempt at a (...) class='Hi'>theory in this field, considering the features and peculiarities of computing science. The fundamental elements of this approach are informons and holons, and it is a general and comprehensive theory of software engineering and knowledge engineering that related disciplines (e.g., information systems) can particularise and/or extend to take benefit from it (Lakatos’ concepts of core theory and protective belt theories). (shrink)

In the article, the philosophical significance of quantum computation theory for philosophy of mathematics is discussed. In particular, I examine the notion of “quantum-assisted proof” (QAP); the discussion sheds light on the problem of the nature of mathematical proof; the potential empirical aspects of mathematics and the realism-antirealism debate (in the context of the indispensability argument). I present a quasi-empiricist account of QAP’s, and discuss the possible impact on the discussions centered around the Enhanced Indispensabity Argument (EIA).

An important link between model theory and proof theory is to construe a deductive disproof of S as an attempted construction of a countermodel to it. In the function logic outlined here, this idea is implemented in such a way that different kinds of individuals can be introduced into the countermodel in any order whatsoever. This imposes connections between the length of the branches of the tree that a disproof is and their number. If there are already n (...) individuals in the countermodel that is being constructed, the next individual has to be considered in its relations to each of the n old ones, creating 2^n different cases and accordingly at least 2^n different branches. Hence a disproof procedure of a polynomial length is normally not equivalent with an exponential one. Because every computation can be represented as a deduction with the same number of constant terms, the same holds for nondeterministic computations. Apparent exceptions seem to come about if a branch created by a new individual i is redundant. But when the disproof is a shortest one (contains the minimum number of different constant terms) then not introducing that idle term at all would result in an even shorter disproof, violating the shortness assumption. (shrink)

The general understanding of pictorial representation as constructed through the viewpoint of the artist outside the picture space is mediated through our present-day familiarity with geometric perspective and photography. This presumes the existence of an external viewpoint. This understanding of painting has become common sense. In this way a 'historical product' has been taken as an 'a-historical essence' of our understanding. Even now, many theories on painting seem to remain caught in such a essentialist thinking. In this paper I discuss (...) the problem of essentialist thinking, basing my views on the philosophy of Kiyoshi Miki, one of the important philosophers of the 'Kyoto School', and then reexamine the belief in the existence of viewpoints outside of painting. (shrink)

In a series of articles we try to show the need of a novel Theory for Theory of Computation based on considering time as a Fuzzy concept. Time is a central concept In Physics. First we were forced to consider some changes and modifications in the Theories of Physics. In the second step and throughout this article we show the positive Impact of this modification on Theory of Computation and Complexity Theory to rebuild it (...) in a more successful and fruitful approach. We call this novel Theory TC*. (shrink)

Throughout this paper, we are trying to show how and why our Mathematical frame-work seems inappropriate to solve problems in Theory of Computation. More exactly, the concept of turning back in time in paradoxes causes inconsistency in modeling of the concept of Time in some semantic situations. As we see in the first chapter, by introducing a version of “Unexpected Hanging Paradox”,first we attempt to open a new explanation for some paradoxes. In the second step, by applying this (...) paradox, it is demonstrated that any formalized system for the Theory of Computation based on Classical Logic and Turing Model of Computation leads us to a contradiction. We conclude that our mathematical frame work is inappropriate for Theory of Computation. Furthermore, the result provides us a reason that many problems in Complexity Theory resist to be solved.(This work is completed in 2017 -5- 2, it is in vixra in 2017-5-14, presented in Unilog 2018, Vichy). (shrink)

Marr's computational theory of stereopsis is shown to imply that human vision employs a system of representation which has all the properties of a number system. Claims for an internal number system and for neural computation should be taken literally. I show how these ideas withstand various skeptical attacks, and analyze the requirements for describing neural operations as computations. Neural encoding of numerals is shown to be distinct from our ability to measure visual physiology. The constructs in Marr's (...) theory are neither propositional nor pictorial, and provide a counter example to many commonly held dichotomies concerning mental representation. (shrink)

We don't yet have adequate theories of what the human mind is representing when it represents a social group. Worse still, many people think we do. This mistaken belief is a consequence of the state of play: Until now, researchers have relied on their own intuitions to link up the conceptsocial groupon the one hand and the results of particular studies or models on the other. While necessary, this reliance on intuition has been purchased at a considerable cost. When looked (...) at soberly, existing theories of social groups are either (i) literal, but not remotely adequate (such as models built atop economic games), or (ii) simply metaphorical (typically a subsumption or containment metaphor). Intuition is filling in the gaps of an explicit theory. This paper presents a computational theory of what, literally, a group representation is in the context of conflict: It is the assignment of agents to specific roles within a small number of triadic interaction types. This “mental definition” of a group paves the way for acomputational theory of social groups– in that it provides a theory of what exactly the information-processing problem of representing and reasoning about a group is. For psychologists, this paper offers a different way to conceptualize and study groups, and suggests that a non-tautological definition of a social group is possible. For cognitive scientists, this paper provides a computational benchmark against which natural and artificial intelligences can be held. (shrink)

One of the most lasting contributions of Marr's posthumous book is his articulation of the different “levels of analysis” that are needed to understand vision. Although a variety of work has examined how these different levels are related, there is comparatively little examination of the assumptions on which his proposed levels rest, or the plausibility of the approach Marr articulated given those assumptions. Marr placed particular significance on computational level theory, which specifies the “goal” of a computation, its (...) appropriateness for solving a particular problem, and the logic by which it can be carried out. The structure of computational level theory is inherently teleological: What the brain does is described in terms of its purpose. I argue that computational level theory, and the reverse-engineering approach it inspires, requires understanding the historical trajectory that gave rise to functional capacities that can be meaningfully attributed with some sense of purpose or goal, that is, a reconstruction of the fitness function on which natural selection acted in shaping our visual abilities. I argue that this reconstruction is required to distinguish abilities shaped by natural selection—“natural tasks” —from evolutionary “by-products”, rather than merely demonstrating that computational goals can be embedded in a Bayesian model that renders a particular behavior or process rational. (shrink)

The widespread belief that the mind is a computer embodies a failure to distinguish between computers and information-processing systems. Minds are information-processing systems, but they are not computers.

We show that the universal theory of the hyperfinite II $_1$ factor is not computable. The proof uses the recent result that MIP*=RE. Combined with an earlier observation of the authors, this yields a proof that the Connes Embedding Problem has a negative solution that avoids the equivalences with Kirchberg’s QWEP Conjecture and Tsirelson’s Problem.

Very plausibly, nothing can be a genuine computing system unless it meets an input-sensitivity requirement. Otherwise all sorts of objects, such as rocks or pails of water, can count as performing computations, even such as might suffice for mentality—thus threatening computationalism about the mind with panpsychism. Maudlin in J Philos 86:407–432, ( 1989 ) and Bishop ( 2002a , b ) have argued, however, that such a requirement creates difficulties for computationalism about conscious experience, putting it in conflict with the (...) very intuitive thesis that conscious experience supervenes on physical activity. Klein in Synthese 165:141–153, ( 2008 ) proposes a way for computationalists about experience to avoid panpsychism while still respecting the supervenience of experience on activity. I argue that his attempt to save computational theories of experience from Maudlin’s and Bishop’s critique fails. (shrink)

This paper deals with the question: What are the criteria that an adequate theory of computation has to meet? 1. Smith's answer: it has to meet the empirical criterion (i.e. doing justice to computational practice), the conceptual criterion (i.e. explaining all the underlying concepts) and the cognitive criterion (i.e. providing solid grounds for computationalism). 2. Piccinini's answer: it has to meet the objectivity criterion (i.e. identifying computation as a matter of fact), the explanation criterion (i.e. explaining the (...) computer's behaviour), the right things compute criterion, the miscomputation criterion (i.e. accounting for malfunctions), the taxonomy criterion (i.e. distinguishing between different classes of computers) and the empirical criterion. 3. Von Neumann's answer: it has to meet the precision and reliability of computers criterion, the single error criterion (i.e. addressing the impacts of errors) and the distinction between analogue and digital computers criterion. 4. “Everything” computes answer: it has to meet the implementation theory criterion by properly explaining the notion of implementation. -/- According to computationalists, minds are computational. Before we can judge the plausibility of any particular computationalist theory, we need to understand what notion of computation this theory employs. Although there are extant accounts of computation, any of which may, in principle, serve as a basis for computationalism, it isn’t clear that they’re all equivalent or even adequate as accounts of computation proper. By examining plausible alternatives to Smith’s adequacy criteria, our goal here is to resist his claim that no adequate account of computation proper is possible. (shrink)

This article reformulates the theory of computable physical models, previously introduced by the author, as a branch of applied model theory in first-order logic. It provides a semantic approach to the philosophy of science that incorporates aspects of operationalism and Popper’s degrees of falsifiability.

The first-order logical theory Th $({\mathbb{N}},x + 1,F(x))$ is proved to be complete for the class ATIME-ALT $(2^{O(n)},O(n))$ when $F(x) = 2^{x}$ , and the same result holds for $F(x) = c^{x}, x^{c} (c \in {\mathbb{N}}, c \ge 2)$ , and F(x) = tower of x powers of two. The difficult part is the upper bound, which is obtained by using a bounded Ehrenfeucht–Fraïssé game.

The aim of this paper is to present some basic notions of the theory of quantum computing and to compare them with the basic notions of the classical theory of computation. I am convinced, that the results of quantum computation theory (QCT) are not only interesting in themselves, but also should be taken into account in discussions concerning the nature of mathematical knowledge. The philosophical discussion will however be postponed to another paper. QCT seems not (...) to be well-known among philosophers (at least not to the degree it deserves), so the aim of this paper is to provide the necessary technical preliminaries presented in a way accessible to the general philosophical audience. (shrink)

What are the conditions under which groups of agents will perform well across multiple tasks? The author establishes a set of “alignment conditions” that enforce identity of beliefs and desires across agents. These conditions are necessary and sufficient for ensuring that a multiagent system behaves as if controlled by a rational centralized controller. Several widely observed social phenomena can be understood as facilitating the alignment conditions.

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)

One of the most debated questions in psychology and cognitive science is the nature and the functioning of the mental processes involved in deductive reasoning. However, all existing theories refer to a specific deductive domain, like syllogistic, propositional or relational reasoning.Our goal is to unify the main types of deductive reasoning into a single set of basic procedures. In particular, we bring together the microtheories developed from a mental models perspective in a single theory, for which we provide a (...) formal foundation. We validate the theory through a computational model (UNICORE) which allows fine‐grained predictions of subjects' performance in different reasoning domains.The performance of the model is tested against the performance of experimental subjects—as reported in the relevant literature—in the three areas of syllogistic, relational and propositional reasoning. The computational model proves to be a satisfactory artificial subject, reproducing both correct and erroneous performance of the human subjects. Moreover, we introduce a developmental trend in the program, in order to simulate the performance of subjects of different ages, ranging from children (3–6) to adolescents (8–12) to adults (>21). The simulation model performs similarly to the subjects of different ages.Our conclusion is that the validity of the mental model approach is confirmed for the deductive reasoning domain, and that it is possible to devise a unique mechanism able to deal with the specific subareas. The proposed computational model (UNICORE) represents such a unifying structure. (shrink)

Whole Trait Theory (and other dynamic theories of personality) can illuminate the process by which motivational states become traits. Mental computational processes constitute part of the explanatory mechanisms that drive trait manifestations. Empirical work on Whole Trait Theory may inform future research directions on mental computational processes.

The Computational Theory of Mind (CTM) holds that the mind is a computer and that cognition is the manipulation of representations. CTM is commonly viewed as the main hypothesis in cognitive science, with classical CTM (related to the Language of Thought Hypothesis) being the most popular variant. However, other computational accounts of the mind either reject LOTH or do not subscribe to RTM. CTM proponents argue that it clarifies how thought and content are causally relevant in the physical world, (...) and they frame this argument in terms of the physical symbol hypothesis, formalism, or syntactic engines. This article focuses on specific problems with CTM, with four main sections covering the introduction of the three main variants of CTM, the most important conceptions of computational explanation in cognitive science, skeptical arguments against CTM raised by Hilary Putnam, and common objections to CTM. (shrink)

The case for computationalism about the mind is in doubt when we acknowledge that there are mental phenomena that require, for a proper accounting, that we get below the level of symbol processing. Such phenomena show us that a computational theory of mind cannot be complete. Chief among these phenomena is emotion.

Theory of mind refers to the human ability to reason about the mental content of other people, such as their beliefs, desires, and goals. People use their theory of mind to understand, reason about, and explain the behaviour of others. Having a theory of mind is especially useful when people collaborate, since individuals can then reason on what the other individual knows as well as what reasoning they might do. Similarly, hybrid intelligence systems, where AI agents collaborate (...) with humans, necessitate that the agents reason about the humans using computational theory of mind. However, to try to keep track of all individual mental attitudes of all other individuals becomes (computationally) very difficult. Accordingly, this paper provides a mechanism for computational theory of mind based on abstractions of single beliefs into higher-level concepts. These abstractions can be triggered by social norms and roles. Their use in decision making serves as a heuristic to choose among interactions, thus facilitating collaboration. We provide a formalization based on epistemic logic to explain how various inferences enable such a computational theory of mind. Using examples from the medical domain, we demonstrate how having such a theory of mind enables an agent to interact with humans effectively and can increase the quality of the decisions humans make. (shrink)