Narrow Results

Limited automata are one-tape Turing machines that are allowed to rewrite the content of any tape cell only in the first d visits, for a fixed constant d. In the case d = 1, namely, when a rewriting is possible only during the first visit to a cell, these models have the same power of finite state automata. We prove state upper and lower bounds for the conversion of 1-limited automata into finite state automata. In particular, we prove a double exponential state gap between nondeterministic 1-limited automata and one-way deterministic finite automata. The gap reduces to a single exponential in the case of deterministic 1-limited automata. This also implies an exponential state gap between nondeterministic and deterministic 1-limited automata. Another consequence is that 1-limited automata can have less states than equivalent two-way nondeterministic finite automata. We show that this is true even if we restrict to the case of the one-letter input alphabet. For each d ≥ 2, d-limited automata are known to characterize the class of context-free languages. Using the Chomsky-Schützenberger representation for contextfree languages, we present a new conversion from context-free languages into 2-limited automata.

We introduce an alternating Turing machine with modified accepting structure (denoted by MATM), which is an alternating Turing machine whose accepting condition differs from that of an ordinary alternating Turing machine (denoted by ATM). An MATM has a set of accepting state sets rather than a set of accepting states. An input word x is accepted by an MATM M if there is a computation tree of M on x such that the set of states associated with the leaves of the tree is equal to an accepting state set. Let UTM (MUTM) denote an ATM (MATM) with no existential state. We first investigate a relationship between ATM’s and MATM’s, and show that (i) for any function L(n), L(n) space bounded on-line (off-line) ATM’s are equivalent to L(n) space bounded on-line (off-line) MATM’s, and (ii) for any L(n) such that L(n)≥log log n and lim_n→∞L(n)/n=0, L(n) space bounded on-line MUTM’s are more powerful than L(n) space bounded on-line UTM’s. We then investigate a relationship between online and off-line, and show for example that for any L(n) such that L(n)≥log n and lim_n→∞L(n)/n=0, L(n) space bounded off-line MUTM’s are more powerful than L(n) space bounded on-line MUTM’s. We next show that there exists an infinite hierarchy among accepting powers of L(n) space bounded on-line (off-line) MATM’s and MUTM’s with L(n)≥log log n and lim_n→∞L(n)/n=0. Finally, we investigate closure properties of space bounded on-line (off-line) MATM’s and MUTM’s.

Systems of uniform recurrence equations were proposed by Karp et al.¹³ as a mean of automatically deriving programs for parallel architectures. Extensions of this formalism are used by many authors in systolic array synthesis. The computability of a system of recurrence equations is therefore of primary importance, and is considered as the first point to be examined when trying to implement an algorithm. This paper investigates the computability of recurrence equations and especially new results obtained in this area. We first recall the definitions of computability proposed by Karp et al.,¹³ Rao,³¹ Joinnault¹² and Saouter et al.³² Then we correct and generalize those results. Finally, we give a new original proof for the undecidability of computability of non-uniform, non-conditional systems of recurrence equations.

We study the computational capabilities of a biologically inspired neural model where the synaptic weights, the connectivity pattern, and the number of neurons can evolve over time rather than stay static. Our study focuses on the mere concept of plasticity of the model so that the nature of the updates is assumed to be not constrained. In this context, we show that the so-called plastic recurrent neural networks (RNNs) are capable of the precise super-Turing computational power — as the static analog neural networks — irrespective of whether their synaptic weights are modeled by rational or real numbers, and moreover, irrespective of whether their patterns of plasticity are restricted to bi-valued updates or expressed by any other more general form of updating. Consequently, the incorporation of only bi-valued plastic capabilities in a basic model of RNNs suffices to break the Turing barrier and achieve the super-Turing level of computation. The consideration of more general mechanisms of architectural plasticity or of real synaptic weights does not further increase the capabilities of the networks. These results support the claim that the general mechanism of plasticity is crucially involved in the computational and dynamical capabilities of biological neural networks. They further show that the super-Turing level of computation reflects in a suitable way the capabilities of brain-like models of computation.

In this paper, a new computation system is defined by coupling a finite automaton with a deterministic Turing machine with one head and one tape that is infinite in one direction only. In a first part of the paper, it is shown that there is a Turing machine with five instructions for which it is possible to devise a finite automaton such that the resulting computation is able to simulate any Turing machine. In a second part of the paper it is shown that if the Turing machine has at most four instructions, whatever the finite automaton is, the halting of the resulting computation is always decidable.

We introduce semaphore codes associated to a Turing machine via resets. Semaphore codes provide an approximation theory for resets. In this paper, we generalize the set-up of our previous paper “Random walks on semaphore codes and delay de Bruijn semigroups” to the infinite case by taking the profinite limit of $k$-resets to obtain $(-\omega )$-resets. We mention how this opens new avenues to attack the vs. NP problem.

In this paper, we investigate the Lindenbaum algebra ℒ(T_fin) of the theory T_fin=Th(M_fin) of the class M_fin of all finite models of a finite rich signature. We prove that this algebra is an atomic Boolean algebra while its Gödel numeration γ is a -numeration. Moreover, the quotient algebra (ℒ(T_fin)/ℱ, γ/ℱ) modulo the Fréchet ideal ℱ is a -algebra, which is universal over the class of all Boolean algebras. These conditions characterize uniquely the algebra ℒ(T_fin); moreover, these conditions characterize up to recursive isomorphism the numerated Boolean quotient algebra (ℒ(T_fin)/ℱ, γ/ℱ).

These results extend the work of Trakhtenbrot [17] and Vaught [18] on the first order theory of the class of all finite models of a finite rich signature.

The universal Turing Machine (TM) is a model for Von Neumann computers — general-purpose computers. A human brain, linked with its biological body, can inside-skull-autonomously learn a universal TM so that he acts as a general-purpose computer and writes a computer program for any practical purposes. It is unknown whether a robot can accomplish the same. This theoretical work shows how the Developmental Network (DN), linked with its robot body, can accomplish this. Unlike a traditional TM, the TM learned by DN is a super TM — Grounded, Emergent, Natural, Incremental, Skulled, Attentive, Motivated, and Abstractive (GENISAMA). A DN is free of any central controller (e.g., Master Map, convolution, or error back-propagation). Its learning from a teacher TM is one transition observation at a time, immediate, and error-free until all its neurons have been initialized by early observed teacher transitions. From that point on, the DN is no longer error-free but is always optimal at every time instance in the sense of maximal likelihood, conditioned on its limited computational resources and the learning experience. This paper extends the Church–Turing thesis to a stronger version — a GENISAMA TM is capable of Autonomous Programming for General Purposes (APFGP) — and proves both the Church–Turing thesis and its stronger version.

The algorithmic unsolvability of the conjugacy problem for finitely presented groups was demonstrated by Novikov in the early 1950s. Various simplifications and alternative proofs were found by later researchers and further questions raised. Recent work by Borovik, Myasnikov and Remeslennikov has considered the question of what proportion of the number of elements of a group (obtained by standard constructions) falls into the realm of unsolvability. In this paper we provide a straightforward construction, as a Britton tower, of a finitely presented group with solvable word problem but unsolvable conjugacy problem of any r.e. (recursively enumerable) Turing degree a. The question of whether two elements are conjugate is bounded truth-table reducible to the question of whether the elements are both conjugate to a single generator of the group. We also define computable normal forms, based on the method of Bokut', that are suitable for the conjugacy problem. We consider (ordered) pairs of normal words U, V for the conjugacy problem whose lengths add to l and show that the proportion of such pairs for which conjugacy is undecidable (in the case a ≠ 0) is strictly less than l²/(2λ - 1)^l where λ > 4.

The construction is based on modular machines, introduced by Aanderaa and Cohen. For the purposes of this construction it was helpful to extend the notion of configuration to include pairs of m-adic integers. The notion of computation step was also extended and is referred to as s-fold computation where s ∈ ℤ (the usual notion coresponds to s = 1). If gcd(m, s) = 1 then determinism is preserved, i.e., if the modular machine is deterministic then it remains so under the extended notion. Furthermore there is a simple correspondence between s-fold and standard computation in this case. Otherwise computation is non-deterministic and there does not seem to be any straightforward correspondence between s-fold and standard computation.

The quest to understand consciousness, once the purview of philosophers and theologians, is now actively pursued by scientists of many stripes. This paper studies consciousness from the perspective of theoretical computer science. It formalizes the Global Workspace Theory (GWT) originated by the cognitive neuroscientist Bernard Baars and further developed by him, Stanislas Dehaene, and others. Our major contribution lies in the precise formal definition of a Conscious Turing Machine (CTM), also called a Conscious AI. We define the CTM in the spirit of Alan Turing’s simple yet powerful definition of a computer, the Turing Machine (TM). We are not looking for a complex model of the brain nor of cognition but for a simple model of (the admittedly complex concept of) consciousness. After formally defining CTM, we give a formal definition of consciousness in CTM. We later suggest why the CTM has the feeling of consciousness. The reasonableness of the definitions and explanations can be judged by how well they agree with commonly accepted intuitive concepts of human consciousness, the range of related concepts that the model explains easily and naturally, and the extent of its agreement with scientific evidence.

Even though simulation models are the dominant paradigm in cognitive science, it has been argued that Galilean models might fare better on both the description and explanation of real cognitive phenomena. The main goal of this paper is to show that the actual construction of Galilean models is clearly feasible, and well suited, for a special class of cognitive phenomena, namely, those of human computation. I will argue in particular that Turing's original formulation of the Church-Turing thesis can naturally be viewed as the core hypothesis of a new empirical theory of human computation. This theory relies on bidimensional Turing machines, a generalization of ordinary machines with one-dimensional tape to two-dimensional paper. Finally, I will suggest that this theory might become a first paradigm for a general approach to the study of cognition, an approach entirely based on Galilean models of cognitive phenomena.

There are many facets to mental life and mental experience. In this chapter, I attempt to account for some central characteristics among those facets. I argue that normative function and representation are emergent in particular forms of the self-maintenance of far from thermodynamic equilibrium systems in their essential far-from-equilibrium conditions. The nature of representation that is thereby modeled — an interactive, pragmatic form — in turn, forces a number of additional properties of mental process, such as consciousness being inherently contentful and from a situated and embodied point of view. In addition, other properties of interactive representation make strong connections with the central nervous system properties that are found to realize mental experience, such as a field organization of oscillatory and mutually modulatory neural processes.

In this chapter I point at a broad analogy between observed behaviour of neuronal firing patterns and structures appearing in complex ecological systems, notably temperate pristine forests. Although such a connection seems at first remote, I will argue that the mosaic-cycle (patch dynamics) concept seems particularly apt at describing universal features common to a wide variety of self organizing hierarchical structures. A simple approach where neurons are represented by connected probabilistic Turing machines will be introduced and related to the mosaic-cycle picture. At a more general level, I will try to sum up some of the generic properties an information processing machine like the brain must possess, including error correcting coding, optimal control, and universal computability. Finally, simple mathematical arguments are given to explain why perception and learning must be active, dialogue like processes.

In this paper we look at links between biology and computer science, at how Turing machines may change our look of bacteria, at how colonies of bacteria could be classified and how hyperbolic cellular automata could be used to better understand the behaviour of colonies of bacteria.