Recent advances on quantum foundations achieved the derivation of free quantum field theory from general principles, without referring to mechanical notions and relativistic invariance. From the aforementioned principles a quantum cellular automata theory follows, whose relativistic limit of small wave-vector provides the free dynamics of quantum field theory. The QCA theory can be regarded as an extended quantum field theory that describes in a unified way all scales ranging from an hypothetical discrete Planck scale (...) up to the usual Fermi scale. The present paper reviews the automaton theory for the Weyl field, and the composite automata for Dirac and Maxwell fields. We then give a simple analysis of the dynamics in the momentum space in terms of a dispersive differential equation for narrowband wave-packets. We then review the phenomenology of the free-field automaton and consider possible visible effects arising from the discreteness of the framework. We conclude introducing the consequences of the automaton dispersion relation, leading to a deformed Lorentz covariance and to possible effects on the thermodynamics of ideal gases. (shrink)

This book bridges the gaps between logic, mathematics and computer science by delving into the theory of well-quasi orders, also known as wqos. This highly active branch of combinatorics is deeply rooted in and between many fields of mathematics and logic, including proof theory, commutative algebra, braid groups, graph theory, analytic combinatorics, theory of relations, reverse mathematics and subrecursive hierarchies. As a unifying concept for slick finiteness or termination proofs, wqos have been rediscovered in diverse contexts, (...) and proven to be extremely useful in computer science. The book introduces readers to the many facets of, and recent developments in, wqos through chapters contributed by scholars from various fields. As such, it offers a valuable asset for logicians, mathematicians and computer scientists, as well as scholars and students. (shrink)

Theory of Computation -- Computation by Abstracts Devices.

As interpreted by Pattee, von Neumann’s Theory of Self-Reproducing Automata has proved to be a useful tool for understanding some of the difficulties and paradoxes of molecular biosemiotics. But is its utility limited to molecular systems or is it more generally applicable within biosemiotics? One way of answering that question is to look at the Theory as a model for one particular high-level biosemiotic activity, human language. If the model is not useful for language, then it certainly (...) cannot be generally useful to biosemiotics. Beginning with the Universal Turing Machine and continuing with von Neumann’s Theory and Pattee’s interpretation, the properties of universality, programmability, underspecification, complementarity of description/construction, and open-ended evolutionary potential are shown to be usefully applicable to language, thus opening a new line of inquiry in biosemiotics. (shrink)

After leading to a new axiomatic derivation of quantum theory, the new informational paradigm is entering the domain of quantum field theory, suggesting a quantum automata framework that can be regarded as an extension of quantum field theory to including an hypothetical Planck scale, and with the usual quantum field theory recovered in the relativistic limit of small wave-vectors. Being derived from simple principles, the automata theory is quantum ab-initio, and does not assume (...) Lorentz covariance and mechanical notions. Being discrete it can describe localized states and measurements, solving all the issues plaguing field theory originated from the continuum. These features make the theory an ideal framework for quantum gravity, with relativistic covariance and space-time emergent solely from the interactions, and not assumed a priori. The paper presents a synthetic derivation of the automata theory, showing how the principles lead to a description in terms of a quantum automaton over a Cayley graph of a group. Restricting to Abelian groups we show how the automata recover the Weyl, Dirac and Maxwell dynamics in the relativistic limit. We conclude with some new routes about the more general scenario of non-Abelian Cayley graphs. The phenomenology arising from the automata theory in the ultra-relativistic domain and the analysis of corresponding distorted Lorentz covariance is reviewed in Bisio et al. (shrink)

In this paper it is argued that certain stimulus-response learning models which are adequate to represent finite automata (acceptors) are not adequate to represent noninitial state input-output automata (transducers). This circumstance suggests the question whether or not the behavior of animals if satisfactorily modelled by automata is predictive. It is argued in partial answer that there are automata which can be explained in the sense that their transition and output functions can be described (roughly, Hempel-type covering (...) law explanation) while their behaviors are in principle not predictable short of possession of their complete histories or of information concerning present internal states by indirect observation. (shrink)

We suggest that developing automata theoretic foundations is relevant for knowledge theory, so that we study not only what is known by agents, but also the mechanisms by which such knowledge is arrived at. We define a class of epistemic automata, in which agents’ local states are annotated with abstract knowledge assertions about others. These are finite state agents who communicate synchronously with each other and information exchange is ‘perfect’. We show that the class of recognizable languages (...) has good closure properties, leading to a Kleene-type theorem using what we call regular knowledge expressions. These automata model distributed causal knowledge in the following way: each agent in the system has a partial knowledge of the temporal evolution of the system, and every time agents synchronize, they update each other’s knowledge, resulting in a more up-to-date view of the system state. Hence we show that these automata can be used to solve the satisfiability problem for a natural epistemic temporal logic for local properties. Finally, we characterize the class of languages recognized by epistemic automata as the regular consistent languages studied in concurrency theory. (shrink)

The first of the authors is an engineer, the second a logician, and they have collaborated to produce a systematic and comprehensive treatise and textbook on the theory of automata—computing machines viewed abstractly—which presupposes only a slight familiarity with logic; there is a long first chapter which develops propositional and predicate logic; the stipulation of logical operators, the "nets" constructed therefrom, and their physical realization comprise the next two chapters. The representation of automata in input-output tables and (...) flow diagrams, and the study of operators in structures come next; the last two chapters concern various practical ways of synthesizing automata and measuring the complexity of logical nets. This is one of the series on logic and foundations of mathematics; the translation from Russian was edited by J. C. Shepherdson.—P. J. M. (shrink)

Cellular automata (henceforth: CA) are discrete, abstract computational systems that have proved useful both as general models of complexity and as more specific representations of non-linear dynamics in a variety of scientific fields. Firstly, CA are (typically) spatially and temporally discrete: they are composed of a finite or denumerable set of homogeneous, simple units, the atoms or cells. At each time unit, the cells instantiate one of a finite set of states. They evolve in parallel at discrete time steps, (...) following state update functions or dynamical transition rules: the update of a cell state obtains by taking into account the states of cells in its local neighborhood (there are, therefore, no actions at a distance). Secondly, CA are abstract, as they can be specified in purely mathematical terms and implemented in physical structures. Thirdly, CA are computational systems: they can compute functions and solve algorithmic problems. Despite functioning in a different way from traditional, Turing machine-like devices, CA with suitable rules can emulate a universal Turing machine, and therefore compute, given Turing's Thesis, anything computable.... (shrink)

A structure has a (finite-string) automatic presentation if the elements of its domain can be named by finite strings in such a way that the coded domain and the coded atomic operations are recognised by synchronous multitape automata. Consequently, every structure with an automatic presentation has a decidable first-order theory. The problems surveyed here include the classification of classes of structures with automatic presentations, the complexity of the isomorphism problem, and the relationship between definability and recognisability.

Finite automata have been recently used as alternative, discrete models in theoretical physics, especially in problems related to the dichotomy between endophysical/intrinsic and exophysical/ extrinsic perception . These studies deal with Moore experiments; the main result states that it is impossible to determine the initial state of an automaton, and, consequently, a discrete model of Heisenberg uncertainty has been suggested. For this aim the classical theory of finite automata — which considers automata with initial states — (...) is not adequate, and a new approach is necessary. A study of finite deterministic automata without initial states is exactly the aim of this paper. We will define and investigate the complexity of various types of simulations between automata. Minimal automata will be constructed and proven to be unique up to an isomorphism. We will build our results on an extension of Myhill-Nerode technique; all constructions will make use of “automata responses” to simple experiments only, i.e., no information about the internal machinery will be considered available. (shrink)

The first of the authors is an engineer, the second a logician, and they have collaborated to produce a systematic and comprehensive treatise and textbook on the theory of automata—computing machines viewed abstractly—which presupposes only a slight familiarity with logic; there is a long first chapter which develops propositional and predicate logic; the stipulation of logical operators, the "nets" constructed therefrom, and their physical realization comprise the next two chapters. The representation of automata in input-output tables and (...) flow diagrams, and the study of operators in structures come next; the last two chapters concern various practical ways of synthesizing automata and measuring the complexity of logical nets. This is one of the series on logic and foundations of mathematics; the translation from Russian was edited by J. C. Shepherdson.—P. J. M. (shrink)

Early modern automata, understood as efforts to ‘model’ life, to grasp its singular properties and/or to unveil and demystify its seeming inaccessibility and mystery, are not just fascinating liminal, boundary, hybrid, crossover or go-between objects, while they are all of those of course. They also pose a direct challenge to some of our common conceptions about mechanism and embodiment. They challenge the simplicity of the distinction between a purported ‘mechanistic’ worldpicture, its ontology and its goals, and on the other (...) hand an attempt to understand ourselves and animals more broadly as flesh-and-blood, affective entities (that is, not just breathing and perspiring, but also desiring and ‘sanguine’ machines, as La Mettrie might have put it). In what follows I reflect on the complexity of early modern mechanism faced with the (living) body, and its mirror image, contemporary theories of embodiment. At times, embodiment theory seems to be governed by a fascination with what the Artificial Life researcher Ezequiel Di Paolo has called ‘biochauvinism’ (Di Paolo, “Extended Life”): an unquestioned belief that ‘living bodies are special’. Yet how does the theorist define this special status? The question is apparently a simple one, or at least promptly yields an aporia which appears simple: to borrow a provocative phrase from Terry Eagleton, embodiment theory is obsessed by the body but terrified of biology. Yet at the same time, at least since Hubert Dreyfus and Andy Clark’s groundbreaking works, embodiment has been a legit part of cognitive science, yielding the even more recently emerged field of ‘embodied cognition’ (see the work of Larry Shapiro), which seeks to depart from traditional cognitive science, especially the latter’s understanding of cognition as computational, in order to instead underscore “the significance of an organism’s body in how and what the organism thinks,” in Shapiro’s words. (shrink)

In this paper, I seek to examine Deleuze’s fascination with “spiritual automata” as a counterpoint to his more famous notion, the “body without organs”. I shall argue that both are grounded in a deep reflection, on Deleuze’s part, on the problems and issues generated by Spinoza’s notion of parallel attributes. Ultimately, I argue, the development of the two notions is motivated by identical metaphysical worries regarding the tenability of transformation, persistence, and affective interrelations between individuals. The answer, for both (...) thinkers, is the insertion of a “third” relational term, which virtually interfaces with each without violation of their parallel development. For Spinoza, such term is the absolutely infinite substance; for Deleuze, it is instead the notion of sense and the faculty of sense-making. (shrink)

The semantic automata framework, developed originally in the 1980s, provides computational interpretations of generalized quantifiers. While recent experimental results have associated structural features of these automata with neuroanatomical demands in processing sentences with quantifiers, the theoretical framework has remained largely unexplored. In this paper, after presenting some classic results on semantic automata in a modern style, we present the first application of semantic automata to polyadic quantification, exhibiting automata for iterated quantifiers. We also discuss the (...) role of semantic automata in linguistic theory and offer new empirical predictions for sentence processing with embedded quantifiers. (shrink)

Complementarity is not only a feature of quantum mechanical systems but occurs also in the context of finite automata.

Complementarity is not only a feature of quantum mechanical systems but occurs also in the context of finite automata.

The semantic automata framework, developed originally in the 1980s, provides computational interpretations of generalized quantifiers. While recent experimental results have associated structural features of these automata with neuroanatomical demands in processing sentences with quantifiers, the theoretical framework has remained largely unexplored. In this paper, after presenting some classic results on semantic automata in a modern style, we present the first application of semantic automata to polyadic quantification, exhibiting automata for iterated quantifiers. We also discuss the (...) role of semantic automata in linguistic theory and offer new empirical predictions for sentence processing with embedded quantifiers. (shrink)

Saul Kripke has proposed an argument to show that there is a serious problem with many computational accounts of physical systems and with functionalist theories in the philosophy of mind. The problem with computational accounts is roughly that they provide no noncircular way to maintain that any particular function with an infinite domain is realized by any physical system, and functionalism has the similar problem because of the character of the functional systems that are supposed to be realized by organisms. (...) This paper shows that the standard account of what it is for a physical system to compute a function can avoid Kripke's criticisms without being reduced to circularity; a very minor and natural elaboration of the standard account suffices to save both functionalist theories and computational accounts generally. (shrink)