Automata, Universality, Computation

Gauss words are finite sequences of letters associated with self-intersecting closed curves in the plane. (These curves have no “triple” self-intersection). These sequences encode the order of intersections on the curves. We characterize, up to homeomorphism, all curves having a given Gauss word. We extend this characterization to the n-tuples of closed curves having a given n-tuple of words, that we call a Gauss multiword. These words encode the self-intersections of the curves and their pairwise intersections. Our characterization uses decompositions of strongly connected graphs in 3-edge-connected components and algebraic terms formalizing these decompositions.

We consider the logical theory of the monoid of subsets of ℕ endowed solely with addition lifted to sets: no other set theoretical predicate or function, no constant (contrarily to previous work by J̇ez and Okhotin cited below). We prove that the class of true Σ₅ formulas is undecidable and that the whole theory is recursively isomorphic to second-order arithmetic. Also, each ultimately periodic set A (viewed as a predicate X = A) is Π₄ definable and their collection is Σ₆. Though these undecidability results are not surprising, they involve technical difficulties witnessed by the following facts: 1) no elementary predicate or operation on sets (inclusion, union, intersection, complementation, adjunction of 0) is definable, 2) The class of subsemigroups is not definable though that of submonoids is easily definable. To get our results, we code integers by a Π₃ definable class of submonoids and arithmetic operations on ℕ by Δ₅ operations on this class.

This paper resulted from a talk I gave at Machines, Computations and Universality 2013 in Zürich and I am very much indebted to the organizers and the participants of this conference for a very fruitful discussion. I am particularly grateful to Maurice Margenstern who, since he was a reader of my PhD, has given me several useful advices related to my work and has often motivated me for inquiring further into problems of decidability and undecidability in the context of tag systems, and more generally, for developing my thoughts on experimental mathematics and computer science

We study position sampling in a 2-way nondeterministic finite automaton (2NFA) to measure the information dependency and information flow between state variables, based on the information-theoretic sampling technique proposed in [16]. We prove that for a 2NFA, the language generated by position sampling is regular. We also show that for a 2NFA, we can effectively find a vector of sampling positions that maximizes dependency and information flow in a run of the 2NFA. Finally, we give some language properties of sampled runs of 2NFAs augmented with restricted unbounded storage.

On the occasion of his 65th birthday we survey some of the work of Maurice Margenstern on small universal Turing machines. Margenstern has been one of the most prolific contributors to this field, having constructed numerous small universal programs for a number of Turing machine models. These positive results are complemented by Margenstern’s negative results, or lower bounds, on universal program size. Finally, he has even explored the space in-between the known program size upper and lower bounds by giving small programs that iterate the Collatz function, which suggests that proving negative results on programs of this size will be at least as hard as resolving the Collatz problem.

A reversible logic element is a primitive for composing reversible computing machines. There are two kinds of such elements, i.e., one without memory, which is commonly called a reversible logic gate, and one with memory. It is known that, in reversible computing, a reversible logic element with memory is useful as well as a reversible logic gate, since reversible computing machines can be constructed simply using such a type of elements. A rotary element (RE) is a typical instance of a reversible logic element with 1-bit memory, whose operations can be easily understood by an intuitive interpretation. In this survey, we discuss how RE is implemented in an idealized reversible physical system, and how reversible Turing machines (RTMs) can be constructed from REs. In particular, we give a new simpler construction method of RTMs than the previous one.

This chapter discusses how the mathematical language used to describe and to observe automatic computations influences the accuracy of the obtained results. The chapter presents results obtained by describing and observing different kinds ofTuringmachines (single andmulti-tape, deterministic and non-deterministic) through the lens of a new mathematical language named Grossone. This emerging language is strongly based on threemethodological ideas borrowed from Physics and applied toMathematics: the distinction between the object (indeedmathematical object) of an observation and the instrument used for this observation; interrelations holding between the object and the tool used for the observation; the accuracy of the observation determined by the tool. In the chapter, the new results are compared to those achievable by using traditional languages. It is shown that both languages do not contradict each other but observe and describe the same object (Turingmachines) but with different accuracies.

We further investigate the parallel array P systems recently introduced by K.G. Subramanian, P. Isawasan, I. Venkat, and L. Pan.We first make explicit several classes of parallel array P systems (with one or more axioms, with total or maximal parallelism, with rules of various types). In this context, some results from the paper by Subramanian et al. mentioned above are improved. Several open problems are formulated.

We present a number of tiny P systems generating or accepting nonsemilinear sets of (vectors of) natural numbers with very small numbers of rules, even for 1, 2, 3, 4, and 5 rules, depending on the particular model and the additional features used in these systems. Among the models we consider are P systems with target agreement and target selection, P systems with promoters and inhibitors, catalytic and purely catalytic P systems with normal catalysts or bi-stable catalysts. We then improve the results for catalytic (purely catalytic) P systems: 14 rules for generating a non-semilinear vector set and 29 rules for generating a non-semilinear number set are sufficient when allowing only the minimal number of two (three) catalysts; only 23 rules are needed if we allow more catalysts, i.e., five (seven) catalysts. Moreover,we introduce the new concept of toxic objects, objects that must not stay idle as otherwise the computation is abandoned without yielding a result. P systems of various kinds using toxic objects allow for smaller descriptional complexity, especially for smaller numbers of rules, as trap rules can be avoided.

In this paper we introduce and study generalized communicating P automata, computing devices that combine properties of classical automata and generalized communicating P systems. We show that certain variants of these constructs are able to accept any recursively enumerable language even with a small number of cells which interact with each other using only one type of very simple communication rules, but there are rescticted types which recognize only the class of regular languages.

In this paper we overview twelve different computational models that use the splicing operation.We explain the methods used for the organization of the computational process in this area and give examples for each considered model.

We delineate the boundary between decidability and undecidability in the context of one-dimensional cellular automata. The key tool for decidability results are automata-theoretic methods, and in particular decision algorithms for automatic structures, that are inherently limited to dealing with a bounded number of steps in the evolution of a configuration. Undecidability and hardness, on the other hand, are closely related to the full orbit problem: does a given configuration appear in the orbit of another?

The CA-w model (cellular automata with write-access) was introduced in order to simplify the description of problemswith dynamic activities, like moving agents or active particles in a grid of cells. This model allows an active cell to send data to a neighboring cell. Thereby neighbors can be activated or deactivated, or the movement of agents can directly be described. The usefulness of the model is demonstrated for basic computational problems, the well-known 1-D CA traffic rule, Pascal’s triangle, Fibonacci numbers, sorting on the ring by agents, and leader election for agents.

The recently introduced Broadcasting Automata model draws inspiration from a variety of sources such as Ad-Hoc radio networks, cellular automata, neighbourhood sequences and nature, employing many of the same pattern forming methods that can be seen in the superposition of waves and resonance. Algorithms for the broadcasting automata model are in the same vain as those encountered in distributed algorithms using a simple notion of waves, messages passed from automata to automata throughout the topology, to construct computations. The waves generated by activating processes in a digital environment can be used for designing a variety of wave algorithms. In this chapter we aim to study the geometrical shapes of informational waves on integer grid generated in broadcasting automata model as well as their potential use for metric approximation in a discrete space. An exploration of the ability to vary the broadcasting radius of each node leads to results of categorisations of digital discs, their form, composition, encodings and generation. Results pertaining to the nodal patterns generated by arbitrary transmission radii on the plane are exploredwith a connection to broadcasting sequences and approximation of discrete metrics of which results are given for the approximation of astroids, a previously unachievable concave metric, through a novel application of the aggregation of waves via a number of explored functions.

For a long time there was little use of prime numbers in practical applications. But nowadays, it has been known that large-scale prime numbers play a very important role in encryption in computer security networks. In this paper, we explore the prime generation problem on cellular automata consisting of infinitely many cells each with finite state memory and present two implementations of real-time prime generators on cellular automata having smallest number of internal states, known at present. It is shown that there exists a real-time prime generator on a 1-bit inter-cell communication cellular automaton with 25-states, which is an improvement over a 34-state implementation given in Umeo and Kamikawa [2003]. In addition,we show that an infinite prime sequence can be generated in real-time by an eight-state cellular automaton with constant-bit communications. Both the algorithms presented are based on the classical sieve of Eratosthenes, and our eight-state implementation is an improvement over a nine-state prime generator developed by Korec [1998]. Those two implementations on cellular automata with different communication models are the smallest realizations in the number of states, at present.

The chapter is an overview of our finding on a novel class of regular automata networks, the phyllosilicate automata. Phyllosilicate is a sheet of silicate tetrahedra bound by basal oxygens. A phyllosilicate automaton is a regular network of finite state machines, which mimics structure of the phyllosilicate. A node of a binary state phyllosilicate automaton takes states 0 and 1. A node updates its state in discrete time depending on a sum of states of its three (silicon nodes) or six (oxygen nodes) closest neighbours. By extensive sampling of the node state transition rule space we classify rules by main types of patterns generated by them based on the patterns shape (convex and concave hulls, almost circularly growing patterns, octagonal patterns, dendritic growth); and, the patterns interior (disordered, solid, labyrinthine). We also present rules exhibiting travelling localizations attributed to Conway’s Game of Life: gliders, oscillators, still lifes, and a glider gun.

Nonconvex optimization is a powerful tool in bioinformatics and computational biology. As an innovative approach to nonconvex programming, Difference of Convex functions (DC) programming and DC Algorithms (DCA) have proved to be efficient for several problems in computational biology. The objective of this chapter is to show that grand challenge problems in bioinformatics and computational biology can be modeled as DC programs and solved by DCA based algorithms. We offer the community of researchers in computational biology promising approaches in a unified DC programming framework to tackle challenging biological problems such as Multiple Alignment of Sequence (MSA), Molecular conformation and Phylogenetic tree reconstruction.