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.

The aim of this paper is to describe and analyze the epistemological justification of a proposal initially made by the biomathematician Robert Rosen in 1958. In this theoretical proposal, Rosen suggests using the mathematical concept of “category” and the correlative concept of “natural equivalence” in mathematical modeling applied to living beings. Our questions are the following: According to Rosen, to what extent does the mathematical notion of category give access to more “natural” formalisms in the modeling of (...) living beings? Is the so -called “naturalness” of some kinds of equivalences (which the mathematical notion of category makes it possible to generalize and to put at the forefront) analogous to the naturalness of living systems? Rosen appears to answer “yes” and to ground this transfer of the concept of “natural equivalence” in biology on such an analogy. But this hypothesis, although fertile, remains debatable. Finally, this paper makes a brief account of the later evolution of Rosen’s arguments about this topic. In particular, it sheds light on the new role played by the notion of “category” in his more recent objections to the computational models that have pervaded almost every domain of biology since the 1990s. (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)

This volume presents the proceedings from the Eleventh Brazilian Logic Conference on Mathematical Logic held by the Brazilian Logic Society in Salvador, Bahia, Brazil. The conference and the volume are dedicated to the memory of professor Mario Tourasse Teixeira, an educator and researcher who contributed to the formation of several generations of Brazilian logicians. Contributions were made from leading Brazilian logicians and their Latin-American and European colleagues. All papers were selected by a careful refereeing processs and were revised and (...) updated by their authors for publication in this volume. There are three sections: Advances in Logic, Advances in Theoretical Computer Science, and Advances in Philosophical Logic. Well-known specialists present original research on several aspects of model theory, proof theory, algebraic logic, category theory, connections between logic and computer science, and topics of philosophical logic of current interest. Topics interweave proof-theoretical, semantical, foundational, and philosophical aspects with algorithmic and algebraic views, offering lively high-level research results. (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)

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)

The Handbook of Computational Social Science is a comprehensive reference source for scholars across multiple disciplines. It outlines key debates in the field, showcasing novel statistical modeling and machine learning methods, and draws from specific case studies to demonstrate the opportunities and challenges in CSS approaches. The Handbook is divided into two volumes written by outstanding, internationally renowned scholars in the field. This first volume focuses on the scope of computational social science, ethics, and case studies. It covers a range (...) of key issues, including open science, formal modeling, and the social and behavioral sciences. This volume explores major debates, introduces digital trace data, reviews the changing survey landscape, and presents novel examples of computational social science research on sensing social interaction, social robots, bots, sentiment, manipulation, and extremism in social media. The volume not only makes major contributions to the consolidation of this growing research field, but also encourages growth into new directions. With its broad coverage of perspectives (theoretical, methodological, computational), international scope, and interdisciplinary approach, this important resource is integral reading for advanced undergraduates, postgraduates and researchers engaging with computational methods across the social sciences, as well as those within the scientific and engineering sectors. (shrink)

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)

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)

Offering an introduction to algorithms, this work considers automata in the context of their applications, NP-completeness, Turing machine notation and Chomsky normal form.

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)

The number of studies related to natural and artificial mechanisms of learning rapidly increases. However, there is no general theory of learning that could provide a unifying basis for exploring different directions in this growing field. For a long time the development of such a theory has been hindered by nativists' belief that the development of a biological organism during ontogeny should be viewed as parameterization of an innate, encoded in the genome structure by an innate algorithm, and (...) nothing essentially new is created during this process. Noam Chomsky has claimed, therefore, that the creation of a non-trivial general mathematical theory of learning is not feasible, since any algorithm cannot produce a more complex algorithm. This study refutes the above argumentation by developing a counter-example based on the mathematical theory of algorithms and computable functions. It introduces a novel concept of a Universal Learning System (ULS) capable of learning to control in an optimal way any given constructive system from a certain class. The necessary conditions for the existence of a ULS and its main functional properties are investigated. The impossibility of building an algorithmic ULS for a sufficiently complex class of controlled objects is shown, and a proof of the existence of a non-algorithmic ULS based on the axioms of classical mathematics is presented. It is argued that a non-algorithmic ULS is a legitimate object of not only mathematics, but also the world of nature. These results indicate that an algorithmic description of the organization and adaptive development of biological systems in general is not sufficient. At the same time, it is possible to create a rigorous non-algorithmic general theory of learning as a theory of ULS. The utilization of this framework for integrating learning-related studies is discussed. (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)

Computational complexity theory is a subfield of computer science originating in computability theory and the study of algorithms for solving practical mathematical problems. Amongst its aims is classifying problems by their degree of difficulty — i.e., how hard they are to solve computationally. This paper highlights the significance of complexity theory relative to questions traditionally asked by philosophers of mathematics while also attempting to isolate some new ones — e.g., about the notion of feasibility in mathematics, (...) the $\mathbf{P} \neq \mathbf{NP}$ problem and why it has proven hard to resolve, and the role of non-classical modes of computation and proof. (shrink)

Despite its significance in neuroscience and computation, McCulloch and Pitts's celebrated 1943 paper has received little historical and philosophical attention. In 1943 there already existed a lively community of biophysicists doing mathematical work on neural networks. What was novel in McCulloch and Pitts's paper was their use of logic and computation to understand neural, and thus mental, activity. McCulloch and Pitts's contributions included (i) a formalism whose refinement and generalization led to the notion of finite automata (an (...) important formalism in computability theory), (ii) a technique that inspired the notion of logic design (a fundamental part of modern computer design), (iii) the first use of computation to address the mind–body problem, and (iv) the first modern computational theory of mind and brain. (shrink)

We live in an information society where the usage, creation, distribution, manipulation, and integration of information is a significant activity. Computations allow us to process information from various sources in various forms and use the derived knowledge in improving efficiency and resilience in our interactions with each other and with our environment. The general theory of information tells us that information to knowledge is as energy is to matter. Energy has the potential to create or modify material structures and (...) information has the potential to create or modify knowledge structures. In this paper, we analyze computations as a vital technological phenomenon of contemporary society which allows us to process and use information. This analysis allows building classifications of computations based on their characteristics and explication of new types of computations. As a result, we extend the existing typologies of computations by delineating novel forms of information representations. While the traditional approach deals only with two dimensions of computation—symbolic and sub-symbolic, here we describe additional dimensions, namely, super-symbolic computation, hybrid computation, fused computation, blended computation, and symbiotic computation. (shrink)

We live in an information society where the usage, creation, distribution, manipulation, and integration of information is a significant activity. Computations allow us to process information from various sources in various forms and use the derived knowledge in improving efficiency and resilience in our interactions with each other and with our environment. The general theory of information tells us that information to knowledge is as energy is to matter. Energy has the potential to create or modify material structures and (...) information has the potential to create or modify knowledge structures. In this paper, we analyze computations as a vital technological phenomenon of contemporary society which allows us to process and use information. This analysis allows building classifications of computations based on their characteristics and explication of new types of computations. As a result, we extend the existing typologies of computations by delineating novel forms of information representations. While the traditional approach deals only with two dimensions of computation—symbolic and sub-symbolic, here we describe additional dimensions, namely, super-symbolic computation, hybrid computation, fused computation, blended computation, and symbiotic computation. (shrink)

We begin by distinguishing computationalism from a number of other theses that are sometimes conflated with it. We also distinguish between several important kinds of computation: computation in a generic sense, digital computation, and analog computation. Then, we defend a weak version of computationalism—neural processes are computations in the generic sense. After that, we reject on empirical grounds the common assimilation of neural computation to either analog or digital computation, concluding that neural computation (...) is sui generis. Analog computation requires continuous signals; digital computation requires strings of digits. But current neuroscientific evidence indicates that typical neural signals, such as spike trains, are graded like continuous signals but are constituted by discrete functional elements (spikes); thus, typical neural signals are neither continuous signals nor strings of digits. It follows that neural computation is sui generis. Finally, we highlight three important consequences of a proper understanding of neural computation for the theory of cognition. First, understanding neural computation requires a specially designed mathematical theory (or theories) rather than the mathematical theories of analog or digital computation. Second, several popular views about neural computation turn out to be incorrect. Third, computational theories of cognition that rely on non-neural notions of computation ought to be replaced or reinterpreted in terms of neural computation. (shrink)

In this paper, I assume, perhaps controversially, that translation into a language of formal logic is not the method by which mathematicians assess mathematical reasoning. Instead, I argue that the actual practice of analyzing, evaluating and critiquing mathematical reasoning resembles, and perhaps equates with, the practice of informal logic or argumentation theory. It doesn’t matter whether the reasoning is a full-fledged mathematical proof or merely some non-deductive mathematical justification: in either case, the methodology of assessment (...) overlaps to a large extent with argument assessment in non-mathematical contexts. I demonstrate this claim by considering the assessment of axiomatic or deductive proofs, probabilistic evidence, computer-aided proofs, and the acceptance of axioms. I also consider Jody Azzouni’s ‘derivation indicator’ view of proofs because it places derivations—which may be thought to invoke formal logic—at the center of mathematical justificatory practice. However, when the notion of ‘derivation’ at work in Azzouni’s view is clarified, it is seen to accord with, rather than to count against, the informal logical view I support. Finally, I pose several open questions for the development of a theory of mathematical argument. (shrink)

The aim of this paper is to show that it’s not a good idea to have a theory of truth that is consistent but ω-inconsistent. In order to bring out this point, it is useful to consider a particular case: Yablo’s Paradox. In theories of truth without standard models, the introduction of the truth-predicate to a first order theory does not maintain the standard ontology. Firstly, I exhibit some conceptual problems that follow from so introducing it. Secondly, I (...) show that in second order theories with standard semantics the same procedure yields a theory that doesn’t have models. So, while having an ω- inconsistent theory is a bad thing, having an unsatisfiable theory of truth is actually worse. This casts doubts on whether the predicate in question is, after all, a truthpredicate for that language. Finally, I present some alternatives to prove an inconsistency adding plausible principles to certain theories of truth. (shrink)

In recent years, several remarkable results have shown that certain theorems of finite combinatorics are unprovable in certain logical systems. These developments have been instrumental in stimulating research in both areas, with the interface between logic and combinatorics being especially important because of its relation to crucial issues in the foundations of mathematics which were raised by the work of Kurt Godel. Because of the diversity of the lines of research that have begun to shed light on these issues, there (...) was a need for a comprehensive overview which would tie the lines together. This volume fills that need by presenting a balanced mixture of high quality expository and research articles that were presented at the August 1985 AMS-IMS-SIAM Joint Summer Research Conference, held at Humboldt State University in Arcata, California.With an introductory survey to put the works into an appropriate context, the collection consists of papers dealing with various aspects of 'unprovable theorems and fast-growing functions'. Among the topics addressed are: ordinal notations, the dynamical systems approach to Ramsey theory, Hindman's finite sums theorem and related ultrafilters, well quasiordering theory, uncountable combinatorics, nonstandard models of set theory, and a length-of-proof analysis of Godel's incompleteness theorem. Many of the articles bring the reader to the frontiers of research in this area, and most assume familiarity with combinatorics and/or mathematical logic only at the senior undergraduate or first-year graduate level. (shrink)

Provability, Computability and Reflection.

This much-needed book provides a thorough account of temporal logic, one of the most important areas of logic in computer science today. The book begins with a solid introduction to semantical and axiomatic approaches to temporal logic. It goes on to cover predicate temporal logic, meta-languages, general theories of axiomatization, many dimensional systems, propositional quantifiers, expressive power, Henkin dimension, temporalization of other logics, and decidability results. With its inclusion of cutting-edge results and unifying methodologies, this book is an indispensable reference (...) for both the pure logician and the theoretical computer scientist. (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)

The problem of how mathematics and physics are related at a foundational level is of interest. The approach taken here is to work towards a coherent theory of physics and mathematics together by examining the theory experiment connection. The role of an implied theory hierarchy and use of computers in comparing theory and experiment is described. The main idea of the paper is to tighten the theory experiment connection by bringing physical theories, as mathematical (...) structures over C, the complex numbers, closer to what is actually done in experimental measurements and computations. The method replaces C by C n which is the set of pairs, R n,I n, of n figure rational numbers in some basis. The properties of these numbers are based on those of numerical measurement outcomes for continuous variables. A model of space and time based on R n is discussed. The model is scale invariant with regions of constant step size interrupted by exponential jumps. A method of taking the limit n→∞ to obtain locally flat continuum-based space and time is outlined. Also R n based space is invariant under scale transformations. These correspond to expansion and contraction of space relative to a flat background. The location of the origin, which is a space and time singularity, does not change under these transformations. Some properties of quantum mechanics, based on C n and on R n space are briefly investigated. (shrink)

Despite claims to the contrary, the science of ecology has a long history of building theories. Many ecological theories are mathematical, computational, or statistical, though, and rarely have attempts been made to organize or extrapolate these models into broader theories. The Theory of Ecology brings together some of the most respected and creative theoretical ecologists of this era to advance a comprehensive, conceptual articulation of ecological theories. The contributors cover a wide range of topics, from ecological niche (...) class='Hi'>theory to population dynamic theory to island biogeography theory. Collectively, the chapters ably demonstrate how theory in ecology accounts for observations about the natural world and how models provide predictive understandings. It organizes these models into constitutive domains that highlight the strengths and weaknesses of ecological understanding. This book is a milestone in ecological theory and is certain to motivate future empirical and theoretical work in one of the most exciting and active domains of the life sciences. (shrink)

Colonius suggests that, in using standard set theory as the language in which to express our computational-level theory of human memory, we would need to violate the axiom of foundation in order to express meaningful memory bindings in which a context is identical to an item in the list. We circumvent Colonius's objection by allowing that a list item may serve as a label for a context without being identical to that context. This debate serves to highlight the (...) value of specifying memory operations in set theoretic notation, as it would have been difficult if not impossible to formulate such an objection at the algorithmic level. (shrink)

This is a concise book that introduces students to the basics of logical thinking and important mathematical structures that are critical for a solid understanding of logical formalisms themselves as well as for building the necessary background to tackle other fields that are based on these logical principles. Despite its compact and small size, it includes many solved problems and quite a few end-of-section exercises that will help readers consolidate their understanding of the material. This textbook is essential reading (...) for anyone interested in the logical foundations of Informatics, Computer Science, Data Science, Artificial Intelligence, and other related areas. Written with undergraduate students in these disciplines in mind, this book can very well serve the needs of interested and curious readers who wish to get a grasp of the logical principles upon which these fields are built. This book does not require readers to possess math skills beyond those learned in high school. (shrink)