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)

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)

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)

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)

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)

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)

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.

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)

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 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 take a deeper dive into two kinds of AI referred to as automata being used to produce music and art. Initially, automata theory was viewed as a model for behavior of neural networks, which were regarded as the mechanistic substrate of intelligence. Some considered the possibility of an artificial neuron, which led to the idea that these networks could be modeled mathematically. Cellular automata and as discussed, evolutionary programming, deal with patterns and regularities that are being (...) employed in AI music production. (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.

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)

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)

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.

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.

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.

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)

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)

In this work we present the algorithms to produce deterministic finite automaton (DFA) for extended operators in regular expressions like intersection, subtraction and complement. The method like "overriding" of the source NFA (NFA not defined) with subset construction rules is used. The past work described only the algorithm for AND-operator(or intersection of regular languages); in this paper the construction for the MINUS-operator (and complement) is shown.

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)

Since the Nuremberg Code and the first Declaration of Helsinki, globally there has been increasing adoption and adherence to procedures for ensuring that human subjects in research are as well informed as possible of the study’s reasons and risks and voluntarily consent to serving as subject. To do otherwise is essentially viewed as violation of the human research subject’s legal and moral rights. However, with the recent philosophical concerns about responsible robotics, the limits and ambiguities of research-subjects ethical codes become (...) apparent on the matter of constructing automata that maximally resemble human beings (as defined hereunder). In this case, the automata themselves, as products of research and development, are in the very process of their construction subjects of research and development. However, such research faces a paradox: The subjects cannot give their informed consent to this research for their own development, although their consent would be needed for the research. According to ethical codes, this research would be unethical. The article then explores whether the background concepts giving rise to this paradox could be reframed in order to allow such research to proceed ethically. (shrink)

The animation-effect of the movement-image constitutes not only a form of life but also a machinic analogue for Husserl's and Kant's accounts of temporality, engendering what Bernard Stiegler calls ‘a cinematography of consciousness’. If autonomous movement is the hallmark of the living being as well as the inanimate mechanism, the movement-image likewise subtends scenes of human and artificial intelligence. Pairing a cybernetic reading of Lacan's mirror stage essay with reflections on the self-recognition dance of Machina Speculatrix (an early example of (...) a biomimetic robot), this essay considers how exosomatic feedback loops enable a kind of ipseity for machinic life as well as the human being as technical being. Despite adopting Derrida's ideas of originary prostheticity and automaticity, rendering living beings as always-already machinic life, Stiegler sets arche-cinema against arche-writing. (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)

In prior papers the following question was considered: which classes of computable sets can be learned if queries about those sets can be asked by the learner? The answer depended on the query language chosen. In this paper we develop a framework for studying this question. Essentially, once we have a result for queries to [S,<]2, we can obtain the same result for many different languages. We obtain easier proofs of old results and several new results. An earlier result we (...) have an easier proof of: the set of computable sets cannot be learned with queries to the language [+,<] . A new result: the set of computable sets cannot be learned with queries to the language [+,<,POWa] where POWa is the predicate that tests if a number is a power of a. (shrink)

In most of the more lively fields of physical enquiry in the first three decades of the seventeenth century, a striking contrast may be observed between the antiquity of the problems attacked, and the innovatory procedures applied to solve them. None of these questions, inherited from a past now remote, seemed more pressing than the time-honoured controversy of the plenum versus the vacuum, especially as the concept of the atomic structure of matter was so closely associated with the existence of (...) the void. The more one studies the arguments produced at that time, the more one will be impressed with the value and importance, for the vacuists and the atomists, of the Pneumatics of Hero of Alexandria. When we read Galileo's explanation of combustion, “the extremely fine particles of fire, penetrating the narrow pores of the metal would fill the minute intervening vacuum, and would set free these minute particles from the forced attraction which these same vacua exert’, we can hear clear echoes of Hero's account of disseminated micro-vacua. Now Hero's work is clearly divided into two sections: a theoretical preface and a collection of 78 “pneumatic devices”. One might be tempted to claim that he, rather than his fellow-atomist Lucretius, inspired the first tentative syntheses of seventeenth-century atomism but it would still be necessary to agree that his chief contributions to the achievements of that generation lie in the experimental techniques which they derived from his instrumentation. Were it not for the popularity of his pneumatic demonstrations, he could never have won such a great reputation as a natural philosopher. Without that reputation, his opinions on this topic would not have been valued as almost equal to those of the mighty Aristotle, especially since he was so decidedly in the minority. (shrink)

In the automata-theoretic approach to verification, we translate specifications to automata. Complexity considerations motivate the distinction between different types of automata. Already in the 60s, it was known that deterministic Büchi word automata are less expressive than nondeterministic Büchi word automata. The proof is easy and can be stated in a few lines. In the late 60s, Rabin proved that Büchi tree automata are less expressive than Rabin tree automata. This proof is much (...) harder. In this work we relate the expressiveness gap between deterministic and nondeterministic Büchi word automata and the expressiveness gap between Büchi and Rabin tree automata. We consider tree automata that recognize derived languages. For a word language L, the derived language of L, denoted L, is the set of all trees all of whose paths are in L. Since often we want to specify that all the computations of the program satisfy some property, the interest in derived languages is clear. Our main result shows that L is recognizable by a nondeterministic Büchi word automaton but not by a deterministic Büchi word automaton iff L is recognizable by a Rabin tree automaton and not by a Büchi tree automaton. Our result provides a simple explanation for the expressiveness gap between Büchi and Rabin tree automata. Since the gap between deterministic and nondeterministic Büchi word automata is well understood, our result also provides a characterization of derived languages that can be recognized by Büchi tree automata. Finally, it also provides an exponential determinization of Büchi tree automata that recognize derived languages. (shrink)

What does it mean to be human in an age of rapid technological advancement? Are we on the brink of transcending our biological limitations, or are we losing touch with the essence of what it means to be human? Emerging technologies challenge our understanding of identity, ethics, and existence. Bringing together leading voices from history, philosophy, science, and ethics, this volume delves into the intricate intersections of transhumanism and posthumanism, offering a thought-provoking exploration of historical and philosophical debates from the (...) Renaissance to the present. It examines how transhumanist thought envisions the enhancement of human capabilities through science and technology, while posthumanism questions the very boundaries that define what it means to be human. A must-read for scholars, students, and anyone intrigued by the future of humanity, this volume is an essential guide to the debates shaping our technological era. (shrink)