While classical temporal logics lose track of a state as soon as a temporal operator is applied, several branching-time logics able to repeatedly refer to a state have been introduced in the literature. We study such logics by introducing a new formalism, hybrid branching-time logics, subsuming the other approaches and making the ability to refer to a state more explicit by assigning a name to it. We analyze the expressive power of hybrid branching-time logics and the complexity of their satisfiability (...) problem. As main result, the satisfiability problem for the hybrid versions of several branching-time logics is proved to be 2EXPTIME -complete. To prove the upper bound, the automata-theoretic approach to branching-time logics is extended to hybrid logics. As a result of independent interest, the nonemptiness problem for alternating one-pebble Büchi tree automata is shown to be 2EXPTIME -complete. A common property of the logics studied is that they refer to only one state. This restriction is crucial: The ability to refer to more than one state causes a nonelementary blow-up in complexity. In particular, we prove that satisfiability for NCTL * has nonelementary complexity. (shrink)

This paper aims at tracking down, by looking at late medieval and early modern discussions over the ontological status of artifacts, the main steps of the process through which nature became theorized on a mechanistic model in the early 17th century. The adopted methodology consists in examining how inventions such as mechanical clocks and automata forced philosophers to modify traditional criteria based on an intrinsic principle of motion and rest for defining natural beings. The paper studies different strategies designed (...) in the transitional period 1300–1600 for making these inventions compatible with classical definitions of nature and artifacts. In the first part of the paper, it is shown that, even if virtually all medieval philosophers acknowledged an ontological distinction between artifacts and natural beings, these different strategies demonstrate a growing concern about the consistency of the art/nature distinction. The next part of the paper studies how mechanical clocks, even before the Scientific Revolution, served as theoretical models for applying mechanistic views to different objects (be they cosmological, physical or biological). The epistemological function of clocks appears to stem from different factors (like the specific manufacturing of late medieval clocks as well as the evolution of 16th-century mechanics) that are listed in this second part of the paper. These factors, combined with the definitional issues raised by automata, explain that clocks became the symbol of a new approach to natural philosophy, characterized by the collapse of the art/nature distinction and the “mechanization of nature”. (shrink)

The free energy principle is sometimes put forward as accounting for biological self-organization and cognition. It states that for a system to maintain non-equilibrium steady-state with its environment it can be described as minimising its free energy. It is said to be entirely scale-free, applying to anything from particles to organisms, and interactive machines, spanning from the abiotic to the biotic. Because the FEP is so general in its application, one might wonder whether this framework can capture anything specific to (...) biology. We take steps to correct for this here. We first explicate the worry, taking pebbles as examples of an abiotic system, and then discuss to what extent the FEP can distinguish its dynamics from an organism’s. We articulate the notion of ‘autonomy as precarious operational closure’ from the enactive literature, and investigate how it can be unpacked within the FEP. This enables the FEP to delineate between the abiotic and the biotic; avoiding the pebble worry that keeps it out of touch with the living systems we encounter in the world. (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)

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)

We provide a translation from SNFPLTL, a normal form for propositional linear time temporal logic, into alternating automata on infinite words, and vice versa. We show this translation has the property that the set of SNFPLTL clauses is satisfiable if and only if the alternating automaton has an accepting run. As there is no direct method known for checking the non-emptiness of alternating automata, the translation to SNFPLTL, together with a temporal proof on the resulting SNFPLTL clauses, provides (...) an indirect non-emptiness check for alternating automata. (shrink)

A lo largo de la historia el ser humano ha sentido interés por el fenómeno del movimiento y su vínculo con la ilusión de vida; diferentes mecanismos y sistemas articulados se han construido con el fin de insuflar vida en seres inertes. El presente artículo reflexiona sobre la cualidad móvil del acto creador presente en diferentes campos socioculturales, desde el misticismo hasta los avances tecnológicos. Se parte del enigma del anima, y su conexión con los creadores, denominados ejecutantes y sus (...) creaciones, denominadas “avatares encarnados”. Se analizan las relaciones de control-libertad, dependencia-independencia entre el ejecutante y su “avatar encarnado”; como también el grado de aceptación que tiene la audiencia al ver las creaciones reproducidas bajo el dispositivo diacrónico. La transición del autómata al personaje animado constata la evolución de los sistemas de representación y reconocimiento del movimiento. (shrink)

After rejecting Carruthers' conflation of levels of consciousness as implausible and conceptually muddled, and Carruthers' claim that nonhumans are automata as undermined by evolutionary and ethological considerations, we develop a general criticism of contemporary philosophical approaches which, though recognizing nonhuman consciousness, still see animals as mere receptacles of experiences. This is, we argue, due to the fact that, while in the case of humans we grant a self - something that has not only a descriptive but also a prescriptive (...) side, requiring at least non-interference - in the case of nonhumans we focus only on the descriptive aspects. Consequently, we treat humans as equals whatever their capacities, but we order nonhumans in a hierarchy based on their cognitive level. We conclude that such double standards are not only inconsistent but also self-serving. (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)

In this paper we present a negative solution of counting problems for some classes slightly different from bounded arithmetic (▵ 0 sets). To get the results we study properties of chains of finite automata.

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)

In some recent papers (G. ‘t Hooft and others), it has been argued that quantum mechanics can arise from classical cellular automata. Nonetheless, G. Shpenkov has proved that the classical wave equation makes it possible to derive a periodic table of elements, which is very close to Mendeleyev’s one, and describe also other phenomena related to the structure of molecules. Hence the classical wave equation complements Schrödinger’s equation, which implies the appearance of a cellular automaton molecular model starting from (...) classical wave equation. The other studies show that the microworld is constituted as a tessellation of primary topological balls. The tessellattice becomes the origin of a submicrospic mechanics in which a quantum system is subdivided to two subsystems: the particle and its inerton cloud, which appears due to the interaction of the moving particle with oncoming cells of the tessellattice. The particle and its inerton cloud periodically change the momentum and hence move like a wave. The new approach allows us to correlate the Klein-Gordon equation with the deformation coat that is formed in the tessellatice around the particle. The submicroscopic approach shows that the source of any type of wave movements including the Klein-Gordon, Schrödinger, and classical wave equations is hidden in the tessellattice and its basic exciations – inertons, carriers of mass and inert properies of matter. We also discuss possible correspondence with Konrad Zuse’s calculating space. (shrink)

The Pebble Limited Partnership proposes to create the Pebble Mine, one of the world’s largest open-pit mines, in the Bristol Bay watershed, home to Alaska’s largest sockeye salmon fishery. De...

Este estudio se ocupa de estrategias deterministas para jugar al Dilema del Prisionero iterado. Cada estrategia se incorpora a la tabla de un autómata de estado finito. Se estudian exhaustivamente tanto las estrategias de 4 bits como las de 16 bits. El estudio de las estrategias de 64 bits se ha hecho por medio de un Algoritmo Genético. Tanto la idea de estudiar estrategias deterministas como la de servirse de un Algoritmo Genético está en Axelrod, _The Complexity of Cooperation_. Respecto (...) a las estrategias de 4 bits, una conclusión se ha impuesto: _Tit for Tat_ no es la estrategia ganadora. Respecto a las estrategias de 16 bits, tampoco _Tit for Tat_ ha resultado ganadora. Respecto a las estrategias de 64 bits, hay que destacar el método de hacer evolucionar los cromosomas encontrados por el Algoritmo Genético confrontándolos con un conjunto de control de estrategias. También hay estrategias de 64 bits mejores que _Tit for Tat._. (shrink)

As engineers propose constructing humanlike automata, the question arises as to whether such machines merit human rights. The issue warrants serious and rigorous examination, although it has not yet cohered into a conversation. To put it into a sure direction, this paper proposes phrasing it in terms of whether humans are morally obligated to extend to maximally humanlike automata full human rights, or those set forth in common international rights documents. This paper’s approach is to consider the ontology (...) of humans and of automata and whether ontological difference between them, that pertains to the very bases of human rights, affects the latter’s claims to full human rights. Considering common bases of human rights, can these bases tell us whether a certain ontological distinction of humans from automata—or a de facto distinction about humans tacitly acknowledged by full-rights-recognizing societies—makes a difference in whether humans are morally obligated to assign these entities full rights? Human rights to security also arise. The conclusion is that humans need not be under any moral obligation to confer full human rights on automata. The paper’s ultimate point is not to close the discussion with this ontological cap but to set a solid moral and legal groundwork for opening it up tout court. (shrink)

Since Aristotle, it has been common to understand wonder as a psychological state characterized by an absence of rational understanding. Drawing on this idea, a number of historians have suggested that the wonder which had long characterized the experience of automata, declined in the early modern period alongside the increased availability of theoretical treatises on mechanics. This article seeks to challenge this view by examining the relationship between rational and practical modes of technical understanding in John Wilkins’ Mathematicall Magick (...) (1648). My aim is to show that a close reading of the second book of the Mathematicall Magick reveals an alternative conception of wonder as an experience of skilled workmanship that both tolerates theoretical understanding and is increased through practical experience. It will be my claim that the conception of technical wonder which emerges from Wilkin’s descriptions of automata, reveals how the concept of Aristotelian wonder is too reductive to capture the variety of ways in which mechanical technology was experienced in early modern England. (shrink)

One of the most important features of living beings that seems universal is perhaps their ability to be modified in a functional way.In order to modelize this characteristic, we designed automata with a finite number of instantaneous internal descriptions, with input(s) and output(s) and which are able to be functionally modified.

From roughly 1965 to 1995, Columbia University's Department of Sociology was a leading center for social study of science, both nationally and internationally. It was often referred to as the Merton School or Columbia School, and four scholars paved its way: Robert K. Merton, Harriet Zuckerman, Stephen Cole, and Jonathan Cole. The goal of the Columbia School was to create and legitimate a new sociological specialty focusing on the scientific community and the growth of scientific knowledge and they did this (...) by exploring the norms, values, and structure of science. The core values of the scientific and university system and the norms attached to them consisted of deeply held beliefs as well as principles that determined how individuals would act. They were organizing principles designed to support the institution in meeting its goals and mission. They influenced the types of social structures that developed to carry out the activities of scientists. Edited by Jonathan R. Cole, this collection of individually and co-authored papers and essays by Cole represents some of the work produced by Cole and his close collaborators over the past 50 years. the essays are contextualized with an introduction by Cole. The pieces in this volume represent the major concerns on the Columbia School, whose focus of attention was not on the production of individual pieces of knowledge, but on the social systems that made that production possible. (shrink)

Sand and Pebbles : The Tales of Muju Ichien, A Voice for Pluralism in Kamakura Buddhism. Robert E. Morrell. State University of New York Press, Albany 1985. xxii + 383 pp. Cloth $39.50; paper $14.95.

We extend some of the classical connections between automata and logic due to Büchi [5] and McNaughton and Papert [12] to languages of finitely varying functions or “signals”. In particular, we introduce a natural class of automata for generating finitely varying functions called ’s, and show that it coincides in terms of language definability with a natural monadic second-order logic interpreted over finitely varying functions Rabinovich [15]. We also identify a “counter-free” subclass of ’s which characterise the first-order (...) definable languages of finitely varying functions. Our proofs mainly factor through the classical results for word languages. These results have applications in automata characterisations for continuously interpreted real-time logics like Metric Temporal Logic Chevalier et al. [6] and [7]. (shrink)

I would like to make some further clarifying remarks about the nature of learning machines, or finite automata as they are more generally known these days. It is clear from much that has recently been written on this subject that there are still many misunderstandings about their capacity and significance.

We investigate structures recognizable by finite state automata with an input tape of length a limit ordinal. At limits, the set of states which appear unboundedly often before the limit are mapped to a limit state. We describe a method for proving non-automaticity and apply this to determine the optimal bounds for the ranks of linear orders recognized by such automata.

First-order logic is known to have a severely limited expressive power on finite structures. As a result, several different extensions have been investigated, including fragments of second-order logic, fixpoint logic, and the infinitary logic L∞ωω in which every formula has only a finite number of variables. In this paper, we study generalized quantifiers in the realm of finite structures and combine them with the infinitary logic L∞ωω to obtain the logics L∞ωω, where Q = {Qi: iε I} is a family (...) of generalized quantifiers on finite structures. Using the logics L∞ωω, we can express polynomial-time properties that are not definable in L∞ωω, such as “there is an even number of x” and “there exists at least n/2 x” , without going to second-order logic. We show that equivalence of finite structures relative to L∞ωω can be characterized in terms of certain pebble games that are a variant of the Ehrenfeucht—Fraïssé games. We combine this game-theoretic characterization with sophisticated combinatorial tools from Ramsey theory, such as van der Waerden's Theorem and Folkman's Theorem, in order to investigate the scope and limits of generalized quantifiers in finite model theory. We obtain sharp lower bounds for expressibility in the logics L∞ωω and discover an intrinsic difference between adding finitely many simple unary generalized quantifiers to L∞ωω adding infinitely many. In particular, we show that if Qis a finite sequence of simple unary generalized quantifiers, then the equicardinality, or Härtig, quantifier is not definable in L∞ωω. We also show that the query “does the equivalence relation E have an even number of equivalence classes” is not definable in the extension L∞ωω of L∞ωω by the Härtig quantifier I and any finite sequence Q of simple unary generalized quantifiers. (shrink)

(2012). Gingerbread Nuts and Pebbles: Frege and the Neo-Kantians – Two Recently Discovered Documents. British Journal for the History of Philosophy. ???aop.label???. doi: 10.1080/09608788.2012.692665.

This book takes a novel look at the topics of school mathematics--arithmetic, geometry, algebra, and calculus. In this stroll on the mathematical seashore we hope to find, quoting Newton, "...a smoother pebble or a prettier shell than ordinary..." This book assembles a collection of mathematical pebbles that are not only curious but also important.

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)

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.

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)

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)

This book brings together researchers from a variety of fields to jointly present and discuss some of the most relevant problems around the conscious mind. This academic plurality perfectly characterizes the complexity with which a current researcher is confronted to discuss and work on this topic. The volume is organized as follows: Part I introduces the general problems of Philosophy of Mind and some historical perspectives. Part II focuses on understanding the input that the empirical sciences can offer to the (...) theoretical problems. Part III discusses some of the core concepts of the field, namely, perception, memory and experience. Part IV debates human and artificial intelligence and, finally, Part V deliberates about the computation and the ethics of big data and artificial intelligence. The book contains valuable material for researchers in several fields such as Cognitive Science and Neuroscience, Psychology and Artificial Intelligence, and Philosophy. It can also be used as a guide to some courses at various levels, from BAs to MAs and PhD courses of several fields. It is our belief, as it is claimed in the preface by Georg Northoff, that there is an urgent need for a truly transdisciplinary exchange between philosophy and the sciences in order to stimulate some real progress. We hope that this book will become a sound step for such an interdisciplinary enterprise. (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)

Cellular Automata (CA) based simulations are widely used in a great variety of domains, fromstatistical physics to social science. They allow for spectacular displays and numerical predictions. Are they forall that a revolutionary modeling tool, allowing for “direct simulation”, or for the simulation of “the phenomenon itself”? Or are they merely models "of a phenomenological nature rather than of a fundamental one”? How do they compareto other modeling techniques? In order to answer these questions, we present a systematic exploration (...) of CA’s various uses. (shrink)

Preservation and interpolation results are obtained for L ∞ω and sublogics $\mathscr{L} \subseteq L_{\infty\omega}$ such that equivalence in L can be characterized by suitable back-and-forth conditions on sets of partial isomorphisms.

We give new examples of FA presentable torsion-free abelian groups. Namely, for every n2, we construct a rank n indecomposable torsion-free abelian group which has an FA presentation. We also construct an FA presentation of the group in which every nontrivial cyclic subgroup is not FA recognizable.