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.

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)

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)

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)

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)

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)

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.

There is a thesis often aired by some philosophers of psychology that syntax is all we need and there is no need to advert to intentional/semantic properties of symbols for purposes of psychological explanation. Indeed, the worry has been present since the first explicit articulation of so-called Computational Theory of Mind (CTM). Even Fodor, who has been the most ardent defender of the Language of Thought Hypoth- esis (LOTH) (which requires the CTM), has raised worries about its apparent consequences. (...) The worry can be put in the form of a question, which Fodor called the. (shrink)

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)

Review of The Computational Theory of Mind by Matteo Colombo and Gualtiero Piccinini. Cambridge, 2023, iv + 75 pp, $64.99 HB.

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.

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)

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)

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)

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.

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)

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

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)

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)

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)

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)

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 (...) semantic software theories are refused to argue in favour of the abductive process of hypothesising and refining models at each level in the hierarchy, until they become satisfactorily predictive. Empirical theories of computational systems are required to be modular, as modular are most software verification and testing activities. We argue that logic relations must be thereby defined among models representing different modules in a semantic theory of a modular software system. We exclude that scientific structuralism is able to define module relations needed in software modular theories. The algebraic Theory of Institutions is finally introduced to specify the logic structure of modular semantic theories of computational systems. (shrink)

A new account of the of the laws of nature based upon Algorithmic Information Theory.

Introduction -- Sanctioning models : theories and their scope -- Methodology for a virtual world -- A tale of two methods -- When theories shake hands -- Models of climate : values and uncertainties -- Reliability without truth -- Conclusion.

This unique book presents a comprehensive and rigorous treatment of the theory of computability which is introductory yet self-contained. It takes a novel approach by looking at the subject using computation models rather than a limitation orientation, and is the first book of its kind to include software. Accompanying software simulations of almost all computational models are available for use in conjunction with the text, and numerous examples are provided on disk in a user-friendly format. Its applications to (...) computer science itself include interesting links to programming language theory, compiler design theory, and algorithm design. The software, numerous examples, and solutions make this book ideal for self-study by computer scientists and mathematicians alike. (shrink)

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)

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)

This book aims to synthesize different directions in knowledge studies into a unified theory of knowledge and knowledge processes. It explicates important relations between knowledge and information. It provides the readers with understanding of the essence and structure of knowledge, explicating operations and process that are based on knowledge and vital for society. The book also highlights how the theory of knowledge paves the way for more advanced design and utilization of computers and networks.

Computers are increasingly interactive. They are no more transformational systems producing a final output after a finite execution. Instead, they continuously react in time to external events that modify the course of computing execution. While philosophers have been interested in conceptualizing computers for a long time, they seem to have paid little attention to the specificities of interactive computing. We propose to tackle this issue by surveying the literature in theoretical computer science, where one can find explicit proposals for a (...) model of interactive computing. In that field, the formal modelling of interactive computing systems has been brought down to whether the new interaction models are reducible to Turing Machines. There are three areas where interaction models are framed. The comparison between TMs and interactive system models is at stake in all of them. These areas are namely some works on concurrency by Milner, on Reactive Turing Machines, and on interaction as a new computing paradigm. For each of the three identified models, we present its motivation, sum up its account for interaction and its legacy, and point out issues regarding the understanding of computers. The survey shows difficulties for epistemologists. The reason is that these analyses focus on the formal equivalence between interactive models of computation and classic ones. Such a project is different from addressing how a computing machine can be interactive: in other words, which mechanisms allow it. (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)

Computation is central to the foundations of modern cognitive science, but its role is controversial. Questions about computation abound: What is it for a physical system to implement a computation? Is computation sufficient for thought? What is the role of computation in a theory of cognition? What is the relation between different sorts of computational theory, such as connectionism and symbolic computation? In this paper I develop a systematic framework that addresses all (...) of these questions. Justifying the role of computation requires analysis of implementation, the nexus between abstract computations and concrete physical systems. I give such an analysis, based on the idea that a system implements a computation if the causal structure of the system mirrors the formal structure of the computation. This account can be used to justify the central commitments of artificial intelligence and computational cognitive science: the thesis of computational sufficiency, which holds that the right kind of computational structure suffices for the possession of a mind, and the thesis of computational explanation, which holds that computation provides a general framework for the explanation of cognitive processes. The theses are consequences of the facts that computation can specify general patterns of causal organization, and mentality is an organizational invariant, rooted in such patterns. Along the way I answer various challenges to the computationalist position, such as those put forward by Searle. I close by advocating a kind of minimal computationalism, compatible with a very wide variety of empirical approaches to the mind. This allows computation to serve as a true foundation for cognitive science. (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)

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)

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)