3rd ed, 2021. A circumscription of the classical theory of computation building up from the Chomsky hierarchy. With the usual topics in formal language and automata theory.

In The Mind Doesn’t Work that Way, Jerry Fodor argues that mental representations have context sensitive features relevant to cognition, and that, therefore, the Classical Computational Theory of Mind (CTM) is mistaken. We call this the Globality Argument. This is an in principle argument against CTM. We argue that it is self-defeating. We consider an alternative argument constructed from materials in the discussion, which avoids the pitfalls of the official argument. We argue that it is also unsound and that, (...) while it is an empirical issue whether context sensitive features of mental representations are relevant to cognition, it is empirically implausible. (shrink)

This is the 3rd edition. Although a number of new technological applications require classical deductive computation with non-classical logics, many key technologies still do well—or exclusively, for that matter—with classical logic. In this first volume, we elaborate on classical deductive computing with classical logic. The objective of the main text is to provide the reader with a thorough elaboration on both classical computing – a.k.a. formal languages and automata theory – and (...) class='Hi'>classical deduction with the classical first-order predicate calculus with a view to computational implementations, namely in automated theorem proving and logic programming. The present third edition improves on the previous ones by providing an altogether more algorithmic approach: There is now a wholly new section on algorithms and there are in total fourteen clearly isolated algorithms designed in pseudo-code. Other improvements are, for instance, an emphasis on functions in Chapter 1 and more exercises with Turing machines. (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)

The problem of emergence in physical theories makes necessary to build a general theory of the relationships between the observed system and the observing system. It can be shown that there exists a correspondence between classical systems and computational dynamics according to the Shannon-Turing model. A classical system is an informational closed system with respect to the observer; this characterizes the emergent processes in classical physics as phenomenological emergence. In quantum systems, the analysis based on the computation (...) theory fails. It is here shown that a quantum system is an informational open system with respect to the observer and able to exhibit processes of observational, radical emergence. Finally, we take into consideration the role of computation in describing the physical world. (shrink)

This chapter draws an analogy between computing mechanisms and autopoietic systems, focusing on the non-representational status of both kinds of system (computational and autopoietic). It will be argued that the role played by input and output components in a computing mechanism closely resembles the relationship between an autopoietic system and its environment, and in this sense differs from the classical understanding of inputs and outputs. The analogy helps to make sense of why we should think of (...) class='Hi'>computing mechanisms as non-representational, and might also facilitate reconciliation between computational and autopoietic/enactive approaches to the study of cognition. (shrink)

There are two versions of the language-of-thought hypothesis (LOT): Representational LOT (roughly, structured representation), introduced by Ockham, and computational LOT (roughly, symbolic computation) introduced by Fodor. Like many others, I oppose the latter but not the former. Quilty-Dunn et al. defend representational LOT, but they do not defend the strong computational LOT thesis central to the classical-connectionist debate.

This volume offers very selected papers from the 2014 conference of the “International Association for Computing and Philosophy” (IACAP) - a conference tradition of 28 years. - - - Table of Contents - 0 Vincent C. Müller: - Editorial - 1) Philosophy of computing - 1 Çem Bozsahin: - What is a computational constraint? - 2 Joe Dewhurst: - Computing Mechanisms and Autopoietic Systems - 3 Vincenzo Fano, Pierluigi Graziani, Roberto Macrelli and Gino Tarozzi: - Are Gandy (...) Machines really local? - 4 Doukas Kapantais: - A refutation of the Church-Turing thesis according to some interpretation of what the thesis says - 5 Paul Schweizer: - In What Sense Does the Brain Compute? - 2) Philosophy of computer science & discovery - 6 Mark Addis, Peter Sozou, Peter C R Lane and Fernand Gobet: - Computational Scientific Discovery and Cognitive Science Theories - 7 Nicola Angius and Petros Stefaneas: - Discovering Empirical Theories of Modular Software Systems. An Algebraic Approach. - 8 Selmer Bringsjord, John Licato, Daniel Arista, Naveen Sundar Govindarajulu and Paul Bello: - Introducing the Doxastically Centered Approach to Formalizing Relevance Bonds in Conditionals - 9 Orly Stettiner: - From Silico to Vitro: - Computational Models of Complex Biological Systems Reveal Real-world Emergent Phenomena - 3) Philosophy of cognition & intelligence - 10 Douglas Campbell: - Why We Shouldn’t Reason Classically, and the Implications for Artificial Intelligence - 11 Stefano Franchi: - Cognition as Higher Order Regulation - 12 Marcello Guarini: - Eliminativisms, Languages of Thought, & the Philosophy of Computational Cognitive Modeling - 13 Marcin Miłkowski: - A Mechanistic Account of Computational Explanation in Cognitive Science and Computational Neuroscience - 14 Alex Tillas: - Internal supervision & clustering: - A new lesson from ‘old’ findings? - 4) Computing & society - 15 Vasileios Galanos: - Floridi/Flusser: - Parallel Lives in Hyper/Posthistory - 16 Paul Bello: - Machine Ethics and Modal Psychology - 17 Marty J. Wolf and Nir Fresco: - My Liver Is Broken, Can You Print Me a New One? - 18 Marty J. Wolf, Frances Grodzinsky and Keith W. Miller: - Robots, Ethics and Software – FOSS vs. Proprietary Licenses. (shrink)

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)

Any computer can create a model of reality. The hypothesis that quantum computer can generate such a model designated as quantum, which coincides with the modeled reality, is discussed. Its reasons are the theorems about the absence of “hidden variables” in quantum mechanics. The quantum modeling requires the axiom of choice. The following conclusions are deduced from the hypothesis. A quantum model unlike a classical model can coincide with reality. Reality can be interpreted as a quantum computer. The physical (...) processes represent computations of the quantum computer. Quantum information is the real fundament of the world. The conception of quantum computer unifies physics and mathematics and thus the material and the ideal world. Quantum computer is a non-Turing machine in principle. Any quantum computing can be interpreted as an infinite classical computational process of a Turing machine. Quantum computer introduces the notion of “actually infinite computational process”. The discussed hypothesis is consistent with all quantum mechanics. The conclusions address a form of neo-Pythagoreanism: Unifying the mathematical and physical, quantum computer is situated in an intermediate domain of their mutual transformation. (shrink)

The paper analyses six ethical challenges posed by cloud computing, concerning ownership, safety, fairness, responsibility, accountability and privacy. The first part defines cloud computing on the basis of a resource-oriented approach, and outlines the main features that characterise such technology. Following these clarifications, the second part argues that cloud computing reshapes some classic problems often debated in information and computer ethics. To begin with, cloud computing makes possible a complete decoupling of ownership, possession and use of (...) data and this helps to explain the problems occurring when different providers of cloud computing retain or relinquish the right to use or own users‘ data. The problem of safety in cloud computing is coupled to that of reliability, insofar as users have to trust providers to preserve their data, applications and content in a reliable manner. It is argued that, in this context, data insurance could play an important role. Regarding fairness, the paper argues that cloud computing is already reshaping the nature of the Digital. Responsibility, accountability and privacy close the ethical analysis of cloud computing. In this case, the thesis is that the necessity to account for the actions of cloud computing users imposes delicate trade-offs between users‘ privacy and the traceability of their operations. (shrink)

In computational complexity theory, decision problems are divided into complexity classes based on the amount of computational resources it takes for algorithms to solve them. In theoretical computer science, it is commonly accepted that only functions for solving problems in the complexity class P, solvable by a deterministic Turing machine in polynomial time, are considered to be tractable. In cognitive science and philosophy, this tractability result has been used to argue that only functions in P can feasibly work as computational (...) models of human cognitive capacities. One interesting area of computational complexity theory is descriptive complexity, which connects the expressive strength of systems of logic with the computational complexity classes. In descriptive complexity theory, it is established that only first-order systems are connected to P, or one of its subclasses. Consequently, second-order systems of logic are considered to be computationally intractable, and may therefore seem to be unfit to model human cognitive capacities. This would be problematic when we think of the role of logic as the foundations of mathematics. In order to express many important mathematical concepts and systematically prove theorems involving them, we need to have a system of logic stronger than classical first-order logic. But if such a system is considered to be intractable, it means that the logical foundation of mathematics can be prohibitively complex for human cognition. In this paper I will argue, however, that this problem is the result of an unjustified direct use of computational complexity classes in cognitive modelling. Placing my account in the recent literature on the topic, I argue that the problem can be solved by considering computational complexity for humanly relevant problem solving algorithms and input sizes. (shrink)

In normative ethical theory, computer ethics belongs to the area of applied ethics dealing with practical and everyday moral problems arising from the use of computers and computer networks in the information society. Modern scholarship usually approves deontological and utilitarian ethics as appropriate to computer ethics, while classical theories of ethics, such as virtue ethics, are usually neglected as anachronistic and unsuitable to the information era and ICT industry. During past decades, an Aristotelian form of virtue ethics has been (...) revived in modern philosophical enquiries with serious attempts for application to computer ethics and cyberethics. In this paper, the author argues that current trends and behaviours in online communication require an ethics of self-care found in Plotinus’ self-centred virtue ethics theory. The paper supports the position that Plotinus’ virtue ethics of intellectual autonomy and self-determination is relevant to cyberethics discussions involved in computer education and online communication. (shrink)

While Thomas Kuhn's theory of scientific revolutions does not specifically deal with validation, the validation of simulations can be related in various ways to Kuhn's theory: 1) Computer simulations are sometimes depicted as located between experiments and theoretical reasoning, thus potentially blurring the line between theory and empirical research. Does this require a new kind of research logic that is different from the classical paradigm which clearly distinguishes between theory and empirical observation? I argue that this is not the (...) case. 2) Another typical feature of computer simulations is their being ``motley'' (Winsberg 2003) with respect to the various premises that enter into simulations. A possible consequence is that in case of failure it can become difficult to tell which of the premises is to blame. Could this issue be understood as fostering Kuhn's mild relativism with respect to theory choice? I argue that there is no need to worry about relativism with respect to computer simulations, in particular. 3) The field of social simulations, in particular, still lacks a common understanding concerning the requirements of empirical validation of simulations. Does this mean that social simulations are still in a pre-scientific state in the sense of Kuhn? My conclusion is that despite ongoing efforts to promote quality standards in this field, lack of proper validation is still a problem of many published simulation studies and that, at least large parts of social simulations must be considered as pre-scientific. (shrink)

In this paper we will demonstrate that a computational system can meet the criteria for autonomy laid down by classical enactivism. The two criteria that we will focus on are operational closure and structural determinism, and we will show that both can be applied to a basic example of a physically instantiated Turing machine. We will also address the question of precariousness, and briefly suggest that a precarious Turing machine could be designed. Our aim in this paper is to (...) challenge the assumption that computational systems are necessarily heteronomous systems, to try and motivate in enactivism a more nuanced and less rigid conception of computational systems, and to demonstrate to computational theorists that they might find some interesting material within the enactivist tradition, despite its historical hostility towards computationalism. (shrink)

Most formalisms for representing common-sense knowledge allow incomplete and potentially inconsistent information. When strong negation is also allowed, contradictory conclusions can arise. A criterion for deciding between them is needed. The aim of this paper is to investigate an inherent and autonomous comparison criterion, based on specificity as defined in [POO 85, SIM 92]. In contrast to other approaches, we consider not only defeasible, but also strict knowledge. Our criterion is context-sensitive, i. e., preference among defeasible rules is determined dynamically (...) during the dialectical analysis.We show how specificity can be defined in terms of two different approaches: activation sets and derivation trees. This allows us to get a syntactic criterion that can be implemented in a computationally attractive way. The resulting definitions may be applied in general rulebased formalisms. We present theorems linking both characterizations. Finally we discuss other frameworks for defeasible reasoning in which preference handling is considered explicitly. (shrink)

This paper proposes an extensionalist analysis of computer simulations (CSs). It puts the emphasis not on languages nor on models, but on symbols, on their extensions, and on their various ways of referring. It shows that chains of reference of symbols in CSs are multiple and of different kinds. As they are distinct and diverse, these chains enable different kinds of remoteness of reference and different kinds of validation for CSs. Although some methodological papers have already underlined the role of (...) these various relationships of reference in CSs and of cross-validations, this diversity is still overlooked in the epistemological literature on CSs. As a consequence, a particular outcome of this analytical view is an ability to classify existing epistemological theses on CSs according to what their authors choose to select and put at the forefront: either the extensions of symbols, or the symbol-types, or the symbol-tokens, or the internal denotational hierarchies of the CS or the reference of these hierarchies to external denotational hierarchies. Through the adoption of this extensionalist view, it also becomes possible to explain more precisely the reasons why some complete reduction of CSs to classical epistemic paradigms such as “experiment” or “theoretical argument” remains doubtful. On this last point, in particular, this paper is in agreement with what many epistemologists already have acknowledged. (shrink)

Logics based on weak Kleene algebra (WKA) and related structures have been recently proposed as a tool for reasoning about flaws in computer programs. The key element of this proposal is the presence, in WKA and related structures, of a non-classical truth-value that is “contaminating” in the sense that whenever the value is assigned to a formula ϕ, any complex formula in which ϕ appears is assigned that value as well. Under such interpretations, the contaminating states represent occurrences of (...) a flaw. However, since different programs and machines can interact with (or be nested into) one another, we need to account for different kind of errors, and this calls for an evaluation of systems with multiple contaminating values. In this paper, we make steps toward these evaluation systems by considering two logics, HYB1 and HYB2, whose semantic interpretations account for two contaminating values beside classical values 0 and 1. In particular, we provide two main formal contributions. First, we give a characterization of their relations of (multiple-conclusion) logical consequence—that is, necessary and sufficient conditions for a set Δ of formulas to logically follow from a set Γ of formulas in HYB1 or HYB2 . Second, we provide sound and complete sequent calculi for the two logics. (shrink)

Both in formal and computational natural language semantics, the classical correspondence view of meaning – and, more specifically, the view that the meaning of a declarative sentence coincides with its truth conditions – is widely held. Truth (in the world or a situation) plays the role of the given, and meaning is analysed in terms of it. Both language and the world feature in this perspective on meaning, but language users are conspicuously absent. In contrast, the inferentialist semantics that (...) Robert Brandom proposes in his magisterial book ‘Making It Explicit’ puts the language user centre stage. According to his theory of meaning, the utterance of a sentence is meaningful in as far as it is a move by a language user in a game of giving and asking for reasons (with reasons underwritten by a notion of good inferences). In this paper, I propose a proof-theoretic formalisation of the game of giving and asking for reasons that lends itself to computer implementation. In the current proposal, I flesh out an account of defeasible inferences, a variety of inferences which play a pivotal role in ordinary (and scientific) language use. (shrink)

At first sight the Theory of Computation i) relies on a kind of mathematics based on the notion of potential infinity; ii) its theoretical organization is irreducible to an axiomatic one; rather it is organized in order to solve a problem: “What is a computation?”; iii) it makes essential use of doubly negated propositions of non-classical logic, in particular in the word expressions of the Church-Turing’s thesis; iv) its arguments include ad absurdum proofs. Under such aspects, it is like (...) many other scientific theories, in particular the first theories of both mechanical machines and heat machines. A more accurate examination of Theory of Computation shows a difference from the above mentioned theories in its essentially including an odd notion, “thesis”, to which no theorem corresponds. On the other hand, arguments of each of the other theories conclude a doubly negative predicate which then, by applying the inverse translation of the ‘negative one’, is translated into the corresponding affirmative predicate. By also taking into account three criticisms to the current Theory of Computation a rational re-formulation of it is sketched out; to Turing-Church thesis of the usual theory corresponds a similar proposition, yet connecting physical total computation functions with constructive mathematical total computation functions. -/- . (shrink)

This paper examines an insoluble Cartesian problem for classical AI, namely, how linguistic understanding involves knowledge and awareness of u’s meaning, a cognitive process that is irreducible to algorithms. As analyzed, Descartes’ view about reason and intelligence has paradoxically encouraged certain classical AI researchers to suppose that linguistic understanding suffices for machine intelligence. Several advocates of the Turing Test, for example, assume that linguistic understanding only comprises computational processes which can be recursively decomposed into algorithmic mechanisms. Against this (...) background, in the first section, I explain Descartes’ view about language and mind. To show that Turing bites the bullet with his imitation game, in the second section I analyze this method to assess intelligence. Then, in the third section, I elaborate on Schank and Abelsons’ Script Applier Mechanism (SAM, hereby), which supposedly casts doubt on Descartes’ denial that machines can think. Finally, in the fourth section, I explore a challenge that any algorithmic decomposition of linguistic understanding faces. This challenge, I argue, is the core of the Cartesian problem: knowledge and awareness of meaning require a first-person viewpoint which is irreducible to the decomposition of algorithmic mechanisms. (shrink)

The paper provides a critical review of the debate on the foundations of Computer Ethics (CE). Starting from a discussion of Moor’s classic interpretation of the need for CE caused by a policy and conceptual vacuum, five positions in the literature are identified and discussed: the “no resolution approach”, according to which CE can have no foundation; the professional approach, according to which CE is solely a professional ethics; the radical approach, according to which CE deals with absolutely unique issues, (...) in need of a unique approach; the conservative approach, according to which CE is only a particular applied ethics, discussing new species of traditional moral issues; and the innovative approach, according to which theoretical CE can expand the metaethical discourse with a substantially new perspective. In the course of the analysis, it is argued that, although CE issues are not uncontroversially unique, they are sufficiently novel to render inadequate the adoption of standard macroethics, such as Utilitarianism and Deontologism, as the foundation of CE and hence to prompt the search for a robust ethical theory. Information Ethics (IE) is proposed for that theory, as the satisfactory foundation for CE. IE is characterised as a biologically unbiased extension of environmental ethics, based on the concepts of information object/infosphere/entropy rather than life/ecosystem/pain. In light of the discussion provided in this paper, it is suggested that CE is worthy of independent study because it requires its own application-specific knowledge and is capable of supporting a methodological foundation, IE. (shrink)

A number of examples have been given of physical systems (both classical and quantum mechanical) which when provided with a (continuously variable) computable input will give a non-computable output. It has been suggested that these systems might allow one to design analogue machines which would calculate the values of some number-theoretic non-computable function. Analysis of the examples show that the suggestion is wrong. In Section 4 I claim that given a reasonable definition of analogue machine it will always be (...) wrong. The claim is to be read not so much as a dogmatic assertion, but rather as a challenge. -/- In Sections 1 and 2 I discuss analogue machines, and lay down some conditions which I believe they must satisfy. In Section I discuss the particular forms which a paradigm undecidable problem (or non-computable function) may take. In Sections 5 and 6 I justify any claim for two particular examples lying within the range of classical physics, and in Section 7 I justify it for two (closely connected) examples from quantum mechanics, and discuss, very briefly, other possible quantum mechanical situations. Section 8 contains various remarks and comments. In Section 9 I consider the suggestion made by Penrose that a (future) theory of quantum gravity may predict non-locally-determined, and perhaps non-computable patterns of growth for microsopic structures. My conclusion is that such a theory will have to have non-computability built into it. (shrink)

Not focusing on the history of classical logic, this book provides discussions and quotes central passages on its origins and development, namely from a philosophical perspective. Not being a book in mathematical logic, it takes formal logic from an essentially mathematical perspective. Biased towards a computational approach, with SAT and VAL as its backbone, this is an introduction to logic that covers essential aspects of the three branches of logic, to wit, philosophical, mathematical, and computational.

A practical viewpoint links reality, representation, and language to calculation by the concept of Turing (1936) machine being the mathematical model of our computers. After the Gödel incompleteness theorems (1931) or the insolvability of the so-called halting problem (Turing 1936; Church 1936) as to a classical machine of Turing, one of the simplest hypotheses is completeness to be suggested for two ones. That is consistent with the provability of completeness by means of two independent Peano arithmetics discussed in Section (...) I. Many modifications of Turing machines cum quantum ones are researched in Section II for the Halting problem and completeness, and the model of two independent Turing machines seems to generalize them. Then, that pair can be postulated as the formal definition of reality therefore being complete unlike any of them standalone, remaining incomplete without its complementary counterpart. Representation is formal defined as a one-to-one mapping between the two Turing machines, and the set of all those mappings can be considered as “language” therefore including metaphors as mappings different than representation. Section III investigates that formal relation of “reality”, “representation”, and “language” modeled by (at least two) Turing machines. The independence of (two) Turing machines is interpreted by means of game theory and especially of the Nash equilibrium in Section IV. Choice and information as the quantity of choices are involved. That approach seems to be equivalent to that based on set theory and the concept of actual infinity in mathematics and allowing of practical implementations. (shrink)

Just as AI has moved away from classical AI, human-computer interaction (HCI) must move away from what I call ‘good old fashioned HCI’ to ‘new HCI’ – it must become a part of cognitive systems research where HCI is one case of the interaction of intelligent agents (we now know that interaction is essential for intelligent agents anyway). For such interaction, we cannot just ‘analyze the data’, but we must assume intentions in the other, and I suggest these are (...) largely recognized through resistance to carrying out one’s own intentions. This does not require fully cognitive agents but can start at a very basic level. New HCI integrates into cognitive systems research and designs intentional systems that provide resistance to the human agent. (shrink)

In this paper we analyze methodological and philosophical implications of algorithmic aspects of unconventional computation. At first, we describe how the classical algorithmic universe developed and analyze why it became closed in the conventional approach to computation. Then we explain how new models of algorithms turned the classical closed algorithmic universe into the open world of algorithmic constellations, allowing higher flexibility and expressive power, supporting constructivism and creativity in mathematical modeling. As Goedels undecidability theorems demonstrate, the closed algorithmic (...) universe restricts essential forms of mathematical cognition. In contrast, the open algorithmic universe, and even more the open world of algorithmic constellations, remove such restrictions and enable new, richer understanding of computation. (shrink)

Throughout this paper, we prove TC+CON(〖TC*〗 )ͰP≠NP. To do that, firstly, we introduce the definition of scope*. This definition is based on the practical situation of computation in the real world. In the real world and real computational activities, we face a finite number of efficiently computable functions which work in a limited time. Inspired by this fact and considering time as a fuzzy concept, we have the definition. By employing this definition, we reach a world of computation in which (...) our time is non-classical and fuzzy, so we have random generations, but the set of all computations (our computational world) is the same as we have in classical time (TC). The result will be P≠NP and P*≠NP*. Throughout this article, we discuss the impact of TC* on TC. -/- . (shrink)

Throughout this paper, we prove TC + CON(TC*)ͰP ≠ NP. To do that, firstly we introduce the definition of scope∗ . This definition is based on the practical situation of computation in the real world. In the real world and real computational activities, we face finite number of efficient computable functions which work in a limited time. Inspired by this fact and considering time as a fuzzy concept, we have the definition. By employing this definition, we reach to a world (...) of computation, in which our time is non-classical and fuzzy, so we have random generations, but the set of all computations (our computational world) is the same as we have in classical time (TC). The result will be P ≠ NP and P* ≠ NP*. Throughout this article, we discuss around the impact of TC* on TC. (shrink)

Throughout this paper, we prove TC+CON(〖TC* 〗)ͰP≠NP. To do that, firstly, we introduce the definition of scope_^*. This definition is based on the practical situation of computation in the real world. In the real world and real computational activities, we face a finite number of efficiently computable functions which work in a limited time. Inspired by this fact and considering time as a fuzzy concept, we have the definition. By employing this definition, we reach a world of computation in which (...) our time is non-classical and fuzzy, so we have random generations, but the set of all computations (our computational world) is the same as we have in classical time (TC). The result will be P≠NP and P*≠NP*. Throughout this article, we discuss around the impact of TC* on TC. (shrink)

Throughout this paper, we prove TC+CON(〖TC〗^* )ͰP≠NP. To do that, firstly, we introduce the definition of scope_^*. This definition is based on the practical situation of computation in the real world. In the real world and real computational activities, we face a finite number of efficiently computable functions which work in a limited time. Inspired by this fact and considering time as a fuzzy concept, we have the definition. By employing this definition, we reach to a world of computation, in (...) which our time is non-classical and fuzzy, so we have random generations, but the set of all computations (our computational world) is the same as we have in classical time (TC). The result will be P≠NP and 〖 P〗^*≠NP^*. Throughout this article, we discuss around the impact of TC^* on TC. (shrink)

2nd edition. Many-valued logics are those logics that have more than the two classical truth values, to wit, true and false; in fact, they can have from three to infinitely many truth values. This property, together with truth-functionality, provides a powerful formalism to reason in settings where classical logic—as well as other non-classical logics—is of no avail. Indeed, originally motivated by philosophical concerns, these logics soon proved relevant for a plethora of applications ranging from switching theory to (...) cognitive modeling, and they are today in more demand than ever, due to the realization that inconsistency and vagueness in knowledge bases and information processes are not only inevitable and acceptable, but also perhaps welcome. The main modern applications of (any) logic are to be found in the digital computer, and we thus require the practical knowledge how to computerize—which also means automate—decisions (i.e. reasoning) in many-valued logics. This, in turn, necessitates a mathematical foundation for these logics. This book provides both these mathematical foundation and practical knowledge in a rigorous, yet accessible, text, while at the same time situating these logics in the context of the satisfiability problem (SAT) and automated deduction. The main text is complemented with a large selection of exercises, a plus for the reader wishing to not only learn about, but also do something with, many-valued logics. (shrink)

The classical theory of computation does not represent an adequate model of reality for simulation in the social sciences. The aim of this paper is to construct a methodological perspective that is able to conciliate the formal and empirical logic of program verification in computer science, with the interpretative and multiparadigmatic logic of the social sciences. We attempt to evaluate whether social simulation implies an additional perspective about the way one can understand the concepts of program and computation. We (...) demonstrate that the logic of social simulation implies at least two distinct types of program verifications that reflect an epistemological distinction in the kind of knowledge one can have about programs. Computer programs seem to possess a causal capability (Fetzer, 1999) and an intentional capability that scientific theories seem not to possess. This distinction is associated with two types of program verification, which we call empirical and intentional verification. We demonstrate, by this means, that computational phenomena are also intentional phenomena, and that such is particularly manifest in agent-based social simulation. Ascertaining the credibility of results in social simulation requires a focus on the identification of a new category of knowledge we can have about computer programs. This knowledge should be considered an outcome of an experimental exercise, albeit not empirical, acquired within a context of limited consensus. The perspective of intentional computation seems to be the only one possible to reflect the multiparadigmatic character of social science in terms of agent-based computational social science. We contribute, additionally, to the clarification of several questions that are found in the methodological perspectives of the discipline, such as the computational nature, the logic of program scalability, and the multiparadigmatic character of agent-based simulation in the social sciences. (shrink)

ABSTRACT A complete axiomatic system CTLrp is introduced for a temporal logic for finitely branching ω+ -trees in a language extended with so called reference pointers. Syntactic and semantic interpretations are constructed for the branching time computation tree logic CTL* into CTLrp. In particular, that yields a complete axiomatization for the translations of all valid CTL*-formulae. Thus, the temporal logic with reference pointers is brought forward as a simpler (with no path quantifiers), but in a way more expressive medium for (...) reasoning about branching time. (shrink)

A complete axiomatic system CTL$_{rp}$ is introduced for a temporal logic for finitely branching $\omega^+$-trees in a temporal language extended with so called reference pointers. Syntactic and semantic interpretations are constructed for the branching time computation tree logic CTL$^{*}$ into CTL$_{rp}$. In particular, that yields a complete axiomatization for the translations of all valid CTL$^{*}$-formulae. Thus, the temporal logic with reference pointers is brought forward as a simpler (with no path quantifiers), but in a way more expressive medium for reasoning (...) about branching time. (shrink)

Background: how mind functions is subject to continuing scientific discussion. A simplistic approach says that, since no convincing way has been found to model subjective experience, mind cannot exist. A second holds that, since mind cannot be described by classical physics, it must be described by quantum physics. Another perspective concerns mind's hypothesized ability to interact with the world of quanta: it should be responsible for reduction of quantum wave packets; physics producing 'Objective Reduction' is postulated to form the (...) basis for mind-matter interactions. This presentation describes results derived from a new approach to these problems. It is based on well-established biology involving physics not previously applied to the fields of mind, or consciousness studies, that of critical feedback instability. -/- Methods: 'self-organized criticality' in complexity biology places system loci of control at critical instabilities, physical properties of which, including information properties, are presented. Their elucidation shows that they can model hitherto unexplained properties of experience. -/- Results: All results depend on physical properties of critical instabilities. First, at least one feed-back or feed-forward loop must have feedback gain, g = 1: information flows round the loop impress perfect images of system states back on themselves: they represent processes of perfect self-observation. This annihilates system quanta: system excitations are instability fluctuations, which cannot be quantized. Major results follow: -/- 1. Information vectors representing criticality states must include at least one attached information loop denoting self-observation. -/- 2. Such loop structures are attributed a function, 'registering the state's own existence', explaining -/- a. Subjective 'awareness of one's own presence' -/- b. How content-free states of awareness can be remembered (Jon Shear) -/- c. Subjective experience of time duration (Immanuel Kant) -/- d. The 'witness' property of experience – often mentioned by athletes 'in the zone' -/- e. The natural association between consciousness and intelligence -/- This novel, physically and biologically sound approach seems to satisfactorily model subjectivity. -/- Further significant results follow: -/- 1. Registration of external information in excited states of systems at criticality reduces external wave-packets: the new model exhibits 'Objective Reduction' of wave packets. -/- 2. High internal coherence (postulated by Domash & Penrose) leading to a. Non-separable information vector bundles. b. Non-reductive states (Chalmers's criterion for experience). -/- 3. Information that is: a. encoded in coherence negentropy; b. non-digitizable, and therefore c. computationally without digital equivalent (posited by Penrose). -/- Discussion and Conclusions: instability physics implies anharmonic motion, preventing excitation quantization, and totally different from the quantum physics of simple harmonic motion at stability. Instability excitations are different from anything hitherto conceived in information science. They can model aspects of mind never previously treated, including genuine subjectivity, objective reduction of wave-packets, and inter alia all properties given above. (shrink)

Endowing artificial systems with explanatory capacities about the reasons guiding their decisions, represents a crucial challenge and research objective in the current fields of Artificial Intelligence (AI) and Computational Cognitive Science [Langley et al., 2017]. Current mainstream AI systems, in fact, despite the enormous progresses reached in specific tasks, mostly fail to provide a transparent account of the reasons determining their behavior (both in cases of a successful or unsuccessful output). This is due to the fact that the classical (...) problem of opacity in artificial neural networks (ANNs) explodes with the adoption of current Deep Learning techniques [LeCun, Bengio, Hinton, 2015]. In this paper we argue that the explanatory deficit of such techniques represents an important problem, that limits their adoption in the cognitive modelling and computational cognitive science arena. In particular we will show how the current attempts of providing explanations of the deep nets behaviour (see e.g. [Ritter et al. 2017] are not satisfactory. As a possibile way out to this problem, we present two different research strategies. The first strategy aims at dealing with the opacity problem by providing a more abstract interpretation of neural mechanisms and representations. This approach is adopted, for example, by the biologically inspired SPAUN architecture [Eliasmith et al., 2012] and by other proposals suggesting, for example, the interpretation of neural networks in terms of the Conceptual Spaces framework [Gärdenfors 2000, Lieto, Chella and Frixione, 2017]. All such proposals presuppose that the neural level of representation can be considered somehow irrelevant for attacking the problem of explanation [Lieto, Lebiere and Oltramari, 2017]. In our opinion, pursuing this research direction can still preserve the use of deep learning techniques in artificial cognitive models provided that novel and additional results in terms of “transparency” are obtained. The second strategy is somehow at odds with respect to the previous one and tries to address the explanatory issue by avoiding to directly solve the “opacity” problem. In this case, the idea is that one of resorting to pre-compiled plausible explanatory models of the word used in combination with deep-nets (see e.g. [Augello et al. 2017]). We argue that this research agenda, even if does not directly fits the explanatory needs of Computational Cognitive Science, can still be useful to provide results in the area of applied AI aiming at shedding light on the models of interaction between low level and high level tasks (e.g. between perceptual categorization and explanantion) in artificial systems. (shrink)

I have read many recent discussions of the limits of computation and the universe as computer, hoping to find some comments on the amazing work of polymath physicist and decision theorist David Wolpert but have not found a single citation and so I present this very brief summary. Wolpert proved some stunning impossibility or incompleteness theorems (1992 to 2008-see arxiv.org) on the limits to inference (computation) that are so general they are independent of the device doing the computation, and even (...) independent of the laws of physics, so they apply across computers, physics, and human behavior. They make use of Cantor's diagonalization, the liar paradox and worldlines to provide what may be the ultimate theorem in Turing Machine Theory, and seemingly provide insights into impossibility, incompleteness, the limits of computation,and the universe as computer, in all possible universes and all beings or mechanisms, generating, among other things,a non- quantum mechanical uncertainty principle and a proof of monotheism. There are obvious connections to the classic work of Chaitin, Solomonoff, Komolgarov and Wittgenstein and to the notion that no program (and thus no device) can generate a sequence (or device) with greater complexity than it possesses. One might say this body of work implies atheism since there cannot be any entity more complex than the physical universe and from the Wittgensteinian viewpoint, ‘more complex’ is meaningless (has no conditions of satisfaction, i.e., truth-maker or test). Even a ‘God’ (i.e., a ‘device’ with limitless time/space and energy) cannot determine whether a given ‘number’ is ‘random’ nor can find a certain way to show that a given ‘formula’, ‘theorem’ or ‘sentence’ or ‘device’ (all these being complex language games) is part of a particular ‘system’. -/- Those wishing a comprehensive up to date framework for human behavior from the modern two systems view may consult my article The Logical Structure of Philosophy, Psychology, Mind and Language as Revealed in Wittgenstein and Searle 59p(2016). For all my articles on Wittgenstein and Searle see my e-book ‘The Logical Structure of Philosophy, Psychology, Mind and Language in Wittgenstein and Searle 367p (2016). Those interested in all my writings in their most recent versions may consult my e-book Philosophy, Human Nature and the Collapse of Civilization - Articles and Reviews 2006-2016’ 662p (2016). -/- All of my papers and books have now been published in revised versions both in ebooks and in printed books. -/- Talking Monkeys: Philosophy, Psychology, Science, Religion and Politics on a Doomed Planet - Articles and Reviews 2006-2017 (2017) https://www.amazon.com/dp/B071HVC7YP. -/- The Logical Structure of Philosophy, Psychology, Mind and Language in Ludwig Wittgenstein and John Searle--Articles and Reviews 2006-2016 (2017) https://www.amazon.com/dp/B071P1RP1B. -/- Suicidal Utopian Delusions in the 21st century: Philosophy, Human Nature and the Collapse of Civilization - Articles and Reviews 2006-2017 (2017) https://www.amazon.com/dp/B0711R5LGX . (shrink)

I have read many recent discussions of the limits of computation and the universe as computer, hoping to find some comments on the amazing work of polymath physicist and decision theorist David Wolpert but have not found a single citation and so I present this very brief summary. Wolpert proved some stunning impossibility or incompleteness theorems (1992 to 2008-see arxiv dot org) on the limits to inference (computation) that are so general they are independent of the device doing the computation, (...) and even independent of the laws of physics, so they apply across computers, physics, and human behavior. They make use of Cantor's diagonalization, the liar paradox and worldlines to provide what may be the ultimate theorem in Turing Machine Theory, and seemingly provide insights into impossibility, incompleteness, the limits of computation, and the universe as computer, in all possible universes and all beings or mechanisms, generating, among other things, a non- quantum mechanical uncertainty principle and a proof of monotheism. There are obvious connections to the classic work of Chaitin, Solomonoff, Komolgarov and Wittgenstein and to the notion that no program (and thus no device) can generate a sequence (or device) with greater complexity than it possesses. One might say this body of work implies atheism since there cannot be any entity more complex than the physical universe and from the Wittgensteinian viewpoint, ‘more complex’ is meaningless (has no conditions of satisfaction, i.e., truth-maker or test). Even a ‘God’ (i.e., a ‘device’with limitless time/space and energy) cannot determine whether a given ‘number’ is ‘random’, nor find a certain way to show that a given ‘formula’, ‘theorem’ or ‘sentence’ or ‘device’ (all these being complex language games) is part of a particular ‘system’. -/- Those wishing a comprehensive up to date framework for human behavior from the modern two systems view may consult my book ‘The Logical Structure of Philosophy, Psychology, Mind and Language in Ludwig Wittgenstein and John Searle’ 2nd ed (2019). Those interested in more of my writings may see ‘Talking Monkeys--Philosophy, Psychology, Science, Religion and Politics on a Doomed Planet--Articles and Reviews 2006-2019 2nd ed (2019) and Suicidal Utopian Delusions in the 21st Century 4th ed (2019) . (shrink)

I critically examine some provocative arguments that John Searle presents in his book The Rediscovery of Mind to support the claim that the syntactic states of a classical computational system are "observer relative" or "mind dependent" or otherwise less than fully and objectively real. I begin by explaining how this claim differs from Searle's earlier and more well-known claim that the physical states of a machine, including the syntactic states, are insufficient to determine its semantics. In contrast, his more (...) recent claim concerns the syntax, in particular, whether a machine actually has symbols to underlie its semantics. I then present and respond to a number of arguments that Searle offers to support this claim, including whether machine symbols are observer relative because the assignment of syntax is arbitrary, or linked to universal realizability, or linked to the sub-personal interpretive acts of a homunculus, or linked to a person's consciousness. I conclude that a realist about the computational model need not be troubled by such arguments. Their key premises need further support. (shrink)

Quantum computing is of high interest because it promises to perform at least some kinds of computations much faster than classical computers. Arute et al. 2019 (informally, “the Google Quantum Team”) report the results of experiments that purport to demonstrate “quantum supremacy” – the claim that the performance of some quantum computers is better than that of classical computers on some problems. Do these results close the debate over quantum supremacy? We argue that they do not. In (...) the following, we provide an overview of the Google Quantum Team’s experiments, then identify some open questions in the quest to demonstrate quantum supremacy. (shrink)

We consider the argument that Tarski's classic definitions permit an intelligence---whether human or mechanistic---to admit finitary evidence-based definitions of the satisfaction and truth of the atomic formulas of the first-order Peano Arithmetic PA over the domain N of the natural numbers in two, hitherto unsuspected and essentially different, ways: (1) in terms of classical algorithmic verifiabilty; and (2) in terms of finitary algorithmic computability. We then show that the two definitions correspond to two distinctly different assignments of satisfaction and (...) truth to the compound formulas of PA over N---I_PA(N; SV ) and I_PA(N; SC). We further show that the PA axioms are true over N, and that the PA rules of inference preserve truth over N, under both I_PA(N; SV ) and I_PA(N; SC). We then show: (a) that if we assume the satisfaction and truth of the compound formulas of PA are always non-finitarily decidable under I_PA(N; SV ), then this assignment corresponds to the classical non-finitary putative standard interpretation I_PA(N; S) of PA over the domain N; and (b) that the satisfaction and truth of the compound formulas of PA are always finitarily decidable under the assignment I_PA(N; SC), from which we may finitarily conclude that PA is consistent. We further conclude that the appropriate inference to be drawn from Goedel's 1931 paper on undecidable arithmetical propositions is that we can define PA formulas which---under interpretation---are algorithmically verifiable as always true over N, but not algorithmically computable as always true over N. We conclude from this that Lucas' Goedelian argument is validated if the assignment I_PA(N; SV ) can be treated as circumscribing the ambit of human reasoning about `true' arithmetical propositions, and the assignment I_PA(N; SC) as circumscribing the ambit of mechanistic reasoning about `true' arithmetical propositions. (shrink)

1. Do models formulated in programming languages use explicit rules where connectionist models do not? 2. Are rules as found in programming languages hard, precise, and exceptionless, where connectionist rules are not? 3. Do connectionist models use rules operating on distributed representations where models formulated in programming languages do not? 4. Do connectionist models fail to use structure sensitive rules of the sort found in "classical" computer architectures? In this chapter we argue that the answer to each of these (...) questions is negative. (shrink)

I review a widely accepted argument to the conclusion that the contents of our beliefs, desires and other mental states cannot be causally efficacious in a classical computational model of the mind. I reply that this argument rests essentially on an assumption about the nature of neural structure that we have no good scientific reason to accept. I conclude that computationalism is compatible with wide semantic causal efficacy, and suggest how the computational model might be modified to accommodate this (...) possibility. (shrink)

The standard view of classical cognitive science stated that cognition consists in the manipulation of language-like structures according to formal rules. Since cognition is ‘linguistic’ in itself, according to this view language is just a complex communication system and does not influence cognitive processes in any substantial way. This view has been criticized from several perspectives and a new framework (Embodied Cognition) has emerged that considers cognitive processes as non-symbolic and heavily dependent on the dynamical interactions between the cognitive (...) system and its environment. But notwithstanding the successes of the embodied cognitive science in explaining low-level cognitive behaviors, it is still not clear whether and how it can scale up for explaining high-level cognition. In this paper we argue that this can be done by considering the role of language as a cognitive tool: i.e. how language transforms basic cognitive functions in the high-level functions that are characteristic of human cognition. In order to do that, we review some computational models that substantiate this view with respect to categorization and memory. Since these models are based on a very rudimentary form of non-syntactic ‘language’ we argue that the use of language as a cognitive tool might have been an early discovery in hominid evolution, and might have played a substantial role in the evolution of language itself. (shrink)

I focus on and criticize John Searle's argument against a classical computational view of the mind according to which the attribution of syntax is observer relative (in Searle, Rediscovery of Mind, MIT Press, 1992). Searle's argument is interesting inasmuch as it differs from his previous and more well-known argument that syntax is not sufficient for semantics. This argument aims to undercut even the syntax as something that exists only in the eye of the beholder. I show that Searle's argument (...) rests on premises that go unsupported. (shrink)

[Müller, Vincent C. (ed.), (2013), Philosophy and theory of artificial intelligence (SAPERE, 5; Berlin: Springer). 429 pp. ] --- Can we make machines that think and act like humans or other natural intelligent agents? The answer to this question depends on how we see ourselves and how we see the machines in question. Classical AI and cognitive science had claimed that cognition is computation, and can thus be reproduced on other computing machines, possibly surpassing the abilities of human (...) intelligence. This consensus has now come under threat and the agenda for the philosophy and theory of AI must be set anew, re-defining the relation between AI and Cognitive Science. We can re-claim the original vision of general AI from the technical AI disciplines; we can reject classical cognitive science and replace it with a new theory (e.g. embodied); or we can try to find new ways to approach AI, for example from neuroscience or from systems theory. To do this, we must go back to the basic questions on computing, cognition and ethics for AI. The 30 papers in this volume provide cutting-edge work from leading researchers that define where we stand and where we should go from here. (shrink)

Could a sufficiently detailed computer simulation of consciousness replicate consciousness? In other words, is performing the right computations sufficient for artificial consciousness? Or will there remain a difference between simulating and being a conscious system, because the right computations must be implemented in the right way? From the perspective of Karl Friston's free energy principle, self-organising systems (such as living organisms) share a set of properties that could be realised in artificial systems, but are not instantiated by computers with a (...) classical (von Neumann) architecture. I argue that at least one of these properties, viz. a certain kind of causal flow, can be used to draw a distinction between systems that merely simulate, and those that actually replicate consciousness. Since this property is instantiated by all systems that conform to the free energy principle (not just conscious beings), the account on offer here can be extended to draw a distinction between simulating and being a certain type of system, more generally. In particular, this may inform meta-ethical accounts of artificial moral status and artificial moral agency. (shrink)

In what way might the new classicism gain support from evolutionary theory? My rough answer is that evolutionary theory can help defend a return to more classical artistic standards and also explain why classical standards are not simply imposed by social conditioning or by powerful elites, but arise naturally from something more fundamental in the human constitution. Classical standards and themes are an expression of our evolutionary history. The mind can be seen as a biological organ or (...) function, produced by evolutionary selection pressure. The most arguable and interesting expression of this point of view is that which says that the human mind is more like a Swiss army knife than a general-purpose computer or sponge for information. Our minds are modular. First propounded by Jerry Fodor, the idea was taken up by evolutionary psychologists and fleshed out with a history. Evolution has given us cognitive modules, partly self-contained mental “machines” that are attuned to solving problems with a narrowly defined domain. Darwinian evolution has shaped our minds in particular ways that fundamentally affect our evaluation of everything we perceive and therefore our appreciation of art. I draw out a surprising implication of combining the modular view with evolution: that our aesthetic standards may, to some extent, be fragmented and not quite as universal as held by the orthodox defence of classical art. (shrink)