Narrow Results

In this paper we consider, from the descriptional complexity point of view, a model of computation introduced in [1], namely accepting network of evolutionary processors with filtered connections (ANEPFCs). First we show that for each morphism h : V → W*, with V ∩ W = ∅, one can effectively construct an ANEPFC, of size 6 + |W|, which accepts every input word w and, at the end of the computation on this word, obtains h(w) in its output node. This result can be applied in constructing two different ANEPFCs, with 27 and, respectively, 26 processors, recognizing a given recursively enumerable language. The first architecture, based on the construction of a universal ANEPFC, has the property that only 7 of its 27 processors depend on the accepted language. On the other hand, all the 26 processors of the second architecture depend on the accepted language, but, differently from the first one, this network simulates efficiently (from both time and space perspectives) a nondeterministic Turing machine accepting the given language.

In this paper we formally define the notion of persistent Turing machines to model interactive computations. We compare the power of persistent Turing machines with respect to computing functions and relations and accepting sets with their classical counterparts. It turns out that the model of persistent computations leads to new characterizations of known function and language classes as well as to classes that have no classical counterpart.

In this paper, we investigate the complexity of computing the detector, constructor and lexicographic constructor functions for a given language. The following classes of languages will be considered: (1) context-free languages, (2) regular sets, (3) languages accepted by one-way nondeterministic auxiliary pushdown automata, (4) languages accepted by one-way nondeterministic logspace-bounded Turing machines, (5) two-way deterministic pushdown automaton languages, (6) languages accepted by uniform families of constant-depth polynomial-size Boolean circuits, and (7) languages accepted by multihead finite automata. We show that for the classes (1)–(4), efficient detectors, constructors and lexicographic constructors exist, whereas for (5)– (7) polynomial-time computable detectors, constructors and lexicographic constructors exist iff there are no sparse sets in NP−P (or equivalently, E=NE). Our results provide sharp boundaries between classes of languages which have efficient detectors, constructors and classes of languages for which efficient detectors and constructors do not appear to exist.

It is shown that the concept of a Universal Computer cannot be realized. Specifically, instances of a computable function are exhibited that cannot be computed on any machine that is capable of only a finite and fixed number of operations per step. This remains true even if the machine is endowed with an infinite memory and the ability to communicate with the outside world while it is attempting to compute . It also remains true if, in addition, is given an indefinite amount of time to compute . This result applies not only to idealized models of computation, such as the Turing Machine and the like, but also to all known general-purpose computers, including existing conventional computers (both sequential and parallel), as well as contemplated unconventional ones such as biological and quantum computers. Even accelerating machines (that is, machines that increase their speed at every step) cannot be universal.

Several nonclosure properties of each class of sets accepted by two-dimensional alternating one-marker automata, alternating one-marker automata with only universal states, nondeterministic one-marker automata, deterministic one-marker automata, alternating finite automata, and alternating finite automata with only universal states are shown. To do this, we first establish the upper bounds of the working space used by "three-way" alternating Turing machines with only universal states to simulate those "four-way" non-storage machines. These bounds provide us a simplified and unified proof method for the whole variants of one-marker and/or alternating finite state machine, without directly analyzing the complex behavior of the individual four-way machine on two-dimensional rectangular input tapes. We also summarize the known closure properties including Boolean closures for all the variants of two-dimensional alternating one-marker automata.

Several nonclosure properties of each class of sets accepted by two-dimensional alternating one-marker automata, alternating one-marker automata with only universal states, nondeterministic one-marker automata, deterministic one-marker automata, alternating finite automata, and alternating finite automata with only universal states are shown. To do this, we first establish the upper bounds of the working space used by "three-way" alternating Turing machines with only universal states to simulate those "four-way" non-storage machines. These bounds provide us a simplified and unified proof method for the whole variants of one-marker and/or alternating finite state machine, without directly analyzing the complex behavior of the individual four-way machine on two-dimensional rectangular input tapes. We also summarize the known closure properties including Boolean closures for all the variants of two-dimensional alternating one-marker automata.

In real life, the increased data accessing speed and data storage ability is required by most of the machinery fields. However, the real-world problems can be studied effectively with the combination of scientific computational techniques with the mathematical models. Automata theory is known to be the popular mathematical model. Towards most of the software and hardware related applications, the computational methods are analyzed and designed using significant automata theory concepts (likely, pushdown automata (PDA), Turing machines (TMs) and finite automata (FA)). Hence, the conventional lecture-driven style has attracted the reflective preferences of learners using these abstract natured concepts. But the lecture-driven teaching style has less motivated the computer engineering learners. In order to learn automata theory and computational models, we introduce the PDA and TM in a virtual platform. However, this work has motivated the improvement of longitudinal experimental validation and learning using the modern technology. Java Formal Languages and Automata Package (JFLAP) tool is used to write our simulators in JAVA language and the results are obtained from each machine through simulating the input strings.

We prove rigorously the four cellular automata local rules 110, 124, 137 and 193 have identical dynamic behaviors capable of universal computations. We exploit Felix Klein's remarkable Vierergruppe to partition the 256 local rules studied empirically by Wolfram into 89 global equivalence classes of which only 50 may exhibit complex dynamics. We define a 24-element rotation group which induces 30 local equivalence classes of nonlinear difference equations whose parameters can be mapped into each other among members of the same class.

By exploiting the new concepts of CA characteristic functions and their associated attractor time-τ maps, a complete characterization of the long-term time-asymptotic behaviors of all 256 one-dimensional CA rules are achieved via a single "probing" random input signal. In particular, the graphs of the time-1 maps of the 256 CA rules represent, in some sense, the generalized Green's functions for Cellular Automata. The asymptotic dynamical evolution on any CA attractor, or invariant orbit, of 206 (out of 256) CA rules can be predicted precisely, by inspection. In particular, a total of 112 CA rules are shown to obey a generalized Bernoulli σ_τ-shift rule, which involves the shifting of any binary string on an attractor, or invariant orbit, either to the left, or to the right, by up to 3 pixels, and followed possibly by a complementation of the resulting bit string.

The most intriguing result reported in this paper is the discovery that the four Turing-universal rules , , , and , and only these rules, exhibit a 1/f power spectrum.

This fifth installment is devoted to an in-depth study of CA Characteristic Functions, a unified global representation for all 256 one-dimensional Cellular Automata local rules. Except for eight rather special local rules whose global dynamics are described by an affine (mod 1) function of only one binary cell state variable, all characteristic functions exhibit a fractal geometry where self-similar two-dimensional substructures manifest themselves, ad infinitum, as the number of cells (I + 1) → ∞.

In addition to a complete gallery of time-1 characteristic functions for all 256 local rules, an accompanying table of explicit formulas is given for generating these characteristic functions directly from binary bit-strings, as in a digital-to-analog converter. To illustrate the potential applications of these fundamental formulas, we prove rigorously that the "right-copycat" local rule is equivalent globally to the classic "left-shift" Bernoulli map. Similarly, we prove the "left-copycat" local rule is equivalent globally to the "right-shift" inverse Bernoulli map.

Various geometrical and analytical properties have been identified from each characteristic function and explained rigorously. In particular, two-level stratified subpatterns found in most characteristic functions are shown to emerge if, and only if, b₁ ≠ 0, where b₁ is the "synaptic coefficient" associated with the cell differential equation developed in Part I.

Gardens of Eden are derived from the decimal range of the characteristic function of each local rule and tabulated. Each of these binary strings has no predecessors (pre-image) and has therefore no past, but only the present and the future. Even more fascinating, many local rules are endowed with binary configurations which not only have no predecessors, but are also fixed points of the characteristic functions. To dramatize that such points have no past, and no future, they are henceforth christened "Isles of Eden". They too have been identified and tabulated.

The aim of this paper is to solve the density classification task (DCT), an extensively studied classical problem, using one-dimensional nonuniform Cellular Automata (CA) rules. A perfect solution of DCT requires searching for CA rules for binary strings of all possible lengths. But the generic problem is still open though the solution exists only for a specific fixed length CA. This paper provides two fundamental ideas to solve this problem in a better way. The first technique solves this problem using deterministic Turing machines which ultimately leads to generation of different CA rules under periodic boundary conditions. In the second technique, the existence of DCT solution by analyzing the state transition diagrams (STDs) of number conserving CA rules is investigated. The possibility of finding the exact solutions of DCT using Turing machine, STD and number conservation property of CA rules can be viewed as an improvement over the approximate solutions obtained by evolutionary techniques.

In this paper, we study the complexity of deciding code and monoid properties for regular sets specified by deterministic or nondeterministic finite automata. The results are as follows. The code problem for regular sets specified by deterministic or nondeterministic finite automata is NL-complete under NC⁽¹⁾ reducibilities. The problems of determining whether a regular set given by a deterministic finite automaton is a monoid or a free monoid or a finitely generated monoid are all NL-complete under NC⁽¹⁾ reducibilities. These monoid problems become PSPACE-complete if the regular sets are specified by nondeterministic finite automata instead. The maximal code problem for deterministic finite automata is shown to be in DET and NL-hard, while a PSPACE upper bound and NP-hardness lower bound hold for the case of nondeterministic finite automata.

We apply driven iterated function system (IFS) to analyze the dynamics of state sequences generated by Turing machines. A topological classification of driven IFS attractors reveals some properties of these state sequences.

The adaptive dynamics is known as a new mathematics to treat with a complex phenomena, for example, chaos, quantum algorithm and psychological phenomena. In this paper, we briefly review the notion of the adaptive dynamics, and explain the definition of the generalized Turing machine (GTM) and recognition process represented by the Fock space. Moreover, we show that there exists the quantum channel which is described by the GKSL master equation to achieve the Chaos Amplifier used in [M. Ohya and I. V. Volovich, J. Opt. B5(6) (2003) 639., M. Ohya and I. V. Volovich, Rep. Math. Phys.52(1) (2003) 25.]

DNA, RNA and proteins are among the most important macromolecules in a living cell. These molecules are polymerized by molecular machines. These natural nano-machines polymerize such macromolecules, adding one monomer at a time, using another linear polymer as the corresponding template. The machine utilizes input chemical energy to move along the template which also serves as a track for the movements of the machine. In the Alan Turing year 2012, it is worth pointing out that these machines are "tape-copying Turing machines". We review the operational mechanisms of the polymerizer machines and their collective behavior from the perspective of statistical physics, emphasizing their common features in spite of the crucial differences in their biological functions. We also draw the attention of the physics community to another class of modular machines that carry out a different type of template-directed polymerization. We hope this review will inspire new kinetic models for these modular machines.

Research is starting to identify correlations between consciousness and some of the spatiotemporal patterns in the physical brain. For theoretical and practical reasons, the results of experiments on the correlates of consciousness have ambiguous interpretations. At any point in time a number of hypotheses co-exist about and the correlates of consciousness in the brain, which are all compatible with the current experimental results. This paper argues that consciousness should be attributed to any system that exhibits spatiotemporal physical patterns that match the hypotheses about the correlates of consciousness that are compatible with the current experimental results. Some computers running some programs should be attributed consciousness because they produce spatiotemporal patterns in the physical world that match those that are potentially linked with consciousness in the human brain.

A mathematical model of classical computer was invented by Alan Turing and named “Turing machine” model, which is an idealized computer with a simple set of instructions and infinite memories. Soon after Turing’s model was proposed, John von Neumann developed a theoretical model for how to implement all the components in a computer to be fully capable as a Turing machine. In more practical way, we will make use of the circuit model, which is useful also in the study of quantum computation. A circuit may involve many inputs, outputs, many wires and many logic gates. These circuits will be implemented by semi-conductors, which have two functions as conductor and insulator and acts under given conditions as a high-speed switch that leads and stops electricity. Modern computers such as personal computers (PC) use integrated circuits (IC) of semiconductor. While the peculiar feature of semiconductor is based entirely on physics of quantum mechanics, we do not call these computers “quantum computers” but rather called “classical computers”, because logic gates are based on binary representations and any quantum state of atom or molecule is not used as a logic gate: in classical computers, the data are represented by two logical values 0 and 1 in the circuits using devices with high voltage/low voltage, current on/off, and/or direction of magnetization up/down.

Several nonclosure properties of each class of sets accepted by two-dimensional alternating one-marker automata, alternating one-marker automata with only universal states, nondeterministic one-marker automata, deterministic one-marker automata, alternating finite automata, and alternating finite automata with only universal states are shown. To do this, we first establish the upper bounds of the working space used by “three-way” alternating Turing machines with only universal states to simulate those “four-way” non-storage machines. These bounds provide us a simplified and unified proof method for the whole variants of one-marker and/or alternating finite state machine, without directly analyzing the complex behavior of the individual four-way machine on two-dimensional rectangular input tapes. We also summarize the known closure properties including Boolean closures for all the variants of two-dimensional alternating one-marker automata.

People always need more information than they have. They can get some of this information by themselves but a good deal of information remains inaccessible. This situation, which always existed in human civilization, brought forth Oracles. The idea of an Oracle reflected interactions between systems, such as people and states, with less information and systems with more indispensable information. In the 20^th century, it was proved that some information is intrinsically inaccessible and then the concept of an Oracle naturally came to computer science becoming popular in the realm of algorithms and computations. At first, Turing machines with an Oracle were introduced and studied. Later inductive Turing machines with Oracles, limit Turing machines with Oracles and evolutionary Turing machines with Oracles were established and explored. Here we create a theoretical background for the concept of an Oracle. In the first part of this work, we contemplate Oracles in human culture. In the second part, we contemplate Oracles in computer science and mathematics. In the third part, the variety of Oracles is analyzed and classified. In the fourth part, we develop a mathematical theory of Oracles, where the concepts of an Oracle and its brands are formalized and studied in the mathematical framework.

The following sections are included:

• Turing machine

• von Neumann computer

• Possibility and complexity of computation
  • Arithmetic operations
    • P problem
  • Factorization and decision of prime numbers
    • About the NP problem
  • Combination problem
    • NP-complete problems
  • Computational complexity and amount of computation

• Logic gates

• Logic circuits

• Sequential circuit and memory

• Problem