Parallel Turing machines on four-dimensional input tapes

The parallel Turing machine (PTM) proposed by Wiedermann is a set of identical usual sequential Turing machines (STMs) cooperating on two common tapes: storage tape and input tape. On the other hand, due to the advances in many application areas such as motion picture processing, computer animation, virtual reality systems, and so forth, it has become increasingly apparent that the study of four-dimensional patterns is of crucial importance. Therefore, we think that the study of four-dimensional automata as a computational model of four-dimensional pattern processing is also meaningful. In this article, we propose a four-dimensional parallel Turing machine (4-PTM), and investigate some of its properties based on hardware complexity.     

Three-dimensional parallel Turing machines

Informally, the parallel Turing machine (PTM) proposed by Wiedermann is a set of identical usual sequential Turing machines (STMs) cooperating on two common tapes: storage tape and input tape. Moreover, STMs which represent the individual processors of a parallel computer can multiply themselves in the course of computation. On the other hand, during the past 25 years or so, automata on a three-dimensional tape have been proposed as computational models of three-dimensional pattern processing, and several properties of such automata have been obtained. We proposed a three-dimensional parallel Turing machine (3-PTM), and dealt with a hardware-bounded 3-PTM whose inputs are restricted to cubic ones. We believe that this machine is useful in measuring the parallel computational complexity of three-dimensional images. In this article, we continue the study of 3-PTM, whose inputs are restricted to cubic ones, and investigate some of its accepting powers. This work was presented in part at the 12th International Symposium on Artificial Life and Robotics, Oita, Japan, January 25–27, 2007     

Some accepting powers of three-dimensional parallel Turing machines

Informally, the parallel Turing machine (PTM) proposed by Wiedermann is a set of identical usual sequential Turing machines (STMs) cooperating on two common tapes: storage tape and input tape. Moreover, STMs which represent the individual processors of a parallel computer can multiply themselves in the course of computation. On the other hand, during the past 25 years or so, automata on a three-dimensional tape have been proposed as computational models of three-dimensional pattern processing, and several properties of such automata have been obtained. We proposed a three-dimensional parallel Turing machine (3-PTM),¹ and dealt with a hardware-bounded 3-PTM whose inputs are restricted to cubic ones. We believe that this machine is useful in measuring the parallel computational complexity of three-dimensional images. Here, we continue the study of 3-PTM, whose inputs are restricted to cubic ones, and investigate some of its accepting powers. This work was presented in part at the First European Workshop on Artificial Life and Robotics, Vienna, Austria, July 12–13, 2007     

Cooperating systems of four-dimensional finite automata

M. Blum and C. Hewitt first proposed two-dimensional automata as a computational model of two-dimensional pattern processing in 1967, and investigated their pattern recognition abilities. Since then, many researchers in this field have investigated many properties of automata on a two- or three-dimensional tape. However, the question of whether processing four-dimensional digital patterns is much more difficult than processing two- or three-dimensional ones is of great interest from both theoretical and practical standpoints. Thus, the study of four-dimensional automata as a computational model of four-dimensional pattern processing has been meaningful. This article introduces a cooperating system of four-dimensional finite automata as one model of four-dimensional automata. A cooperating system of four-dimensional finite automata consists of a finite number of four-dimensional finite automata and a four-dimensional input tape, where these finite automata work independently (in parallel). The finite automata whose input heads scan the same cell of the input tape can communicate with each other, i.e., every finite automaton is allowed to know the internal states of other finite automata on the cell it is scanning at the moment. In this article we mainly investigate the accepting powers of a cooperating system of seven-way four-dimensional finite automata. The seven-way four-dimensional finite automaton is a four-dimensional finite automaton whose input head can move east, west, south, north, up, down, or in the future, but not in the past, on a four-dimensional input tape.     

Bottom-up pyramid cellular acceptors with four-dimensional layers

In 1967, M. Blum and C. Hewitt first proposed two-dimensional automata as a computational model of two-dimensional pattern processing. Since then, many researchers in this field have been investigating the many properties of two- or three-dimensional automata. In 1977, C.R. Dyer and A. Rosenfeld introduced an acceptor on a two-dimensional pattern (or tape) called the pyramid cellular acceptor, and demonstrated that many useful recognition tasks are executed by pyramid cellular acceptors in a time which is proportional to the logarithm of the diameter of the input. They also introduced a bottom-up pyramid cellular acceptor, which is a restricted version of the pyramid cellular acceptor, and proposed some interesting open problems about bottom-up pyramid cellular acceptors. On the other hand, we think that the study of four-dimensional automata has been meaningful as the computational model of four-dimensional information processing such as computer animation, moving picture processing, and so forth. In this article, we investigate bottom-up pyramid cellular acceptors with four-dimensional layers, and show some of their accepting powers.     

Parallel image processing by memory-augmented cellular automata

This paper introduces a generalization of cellular automata in which each celi is a tape-bounded Turing machine rather than a finite-state machine. Fast algorithms are given for performing various basic image processing tasks by such automata. It is suggested that this model of parallel computation is a very suitable one for studying the advantages of parallelism in this domain.     

Two tapes versus one for off-line Turing machines

We prove the first superlinear lower bound for a concrete, polynomial time recognizable decision problem on a Turing machine with one work tape and a two-way input tape (also called off-line 1-tape Turing machine).In particular, for off-line Turing machines we show that two tapes are better than one and that three pushdown stores are better than two (both in the deterministic and in the nondeterministic case).     

Hierarchies based on the number of cooperating systems of three-dimensional finite automata

The question of whether processing three-dimensional digital patterns is much more difficult than two-dimensional ones is of great interest from both theoretical and practical standpoints. Recently, owing to advances in many application areas, such as computer vision, robotics, and so forth, it has become increasingly apparent that the study of three-dimensional pattern processing is of crucial importance. Thus, the study of three-dimensional automata as a computational model of three-dimensional pattern processing has become meaningful. This article introduces a cooperating system of three-dimensional finite automata as one model of three-dimensional automata. A cooperating system of three-dimensional finite automata consists of a finite number of three-dimensional finite automata and a three-dimensional input tape where these finite automata work independently (in parallel). Those finite automata whose input heads scan the same cell of the input tape can communicate with each other, i.e., every finite automaton is allowed to know the internal states of other finite automata on the cell it is scanning at the moment. In this article, we continue the study of cooperating systems of three-dimensional finite automata, and mainly investigate hierarchies based on the number of their cooperating systems.     

Design and simulation of quantum-dot cellular automata serial decimal pipelined processor based on Turing machine model

The quantum-dot cellular automata (QCA) nanoscale computer technology is promising to overcome the limits of the microelectronic CMOS technology. Because the leading role of QCA wires, the serial data transfer/processing is preferable. The financial, Internet of Things, and control computer applications require direct processing of decimal information without representation and conversion errors. Because a QCA wire can be considered as a virtual tape with written binary symbols, a special version of Turing machine model can be used for a QCA computer implementation. Design of a novel QCA serial decimal pipelined processor based on the Turing machine model is presented. The processor uses the run-time tape reconfiguration for arithmetic processing of decimal operands encoded in the 5-bit Johnson-Mobius code. The proposed design demonstrates significant hardware simplification.     

On parallel Turing machines with multi-head control units

This paper deals with parallel Turing machines with multi-head control units on one or more tapes which can be considered as a generalization of cellular automata. We discuss the problem of finding an appropriate measure of space complexity. A definition is suggested which implies that the model is in the first machine class. It is shown that without loss of generality it suffices to consider only parallel Turing machines of certain normal forms.     

Periodicity in generations of automata

A class of automata which build other automata is defined. These automata are called Turing machine automata because each one contains a Turing machine which acts as its computer-brain and which completely determines what its offspring, if any, will be. We show that for the descendants of an arbitrary progenitor Turing machine automaton there are exactly three possibilities: (1) there is a sterile descendant after an arbitrary number of generations, (2) after a delay of an arbitrary number of generations, the descendants repeat in generations with an arbitrary period, or (3) the descendants are aperiodic. We also show what sort of computing ability may be realized by the descendants in each of the possibilities. Furthermore, it is determined whether there are effective procedures for distinguishing between the various possibilities, and the exact degree of unsolvability is computed for those decision problems for which there is no effective procedure. Lastly, we discuss the relevance of the results to biology and pose several questions.Department of Computer Science. The research for this paper was supported in part by Kansas General Research Grant 3683-5038.     

Alternation on cellular automata

In this paper we consider several notions of alternation in cellular automata: non-uniform, uniform and weak alternation. We study relations among these notions and with alternating Turing machines. It is proved that the languages accepted in polynomial time by alternating Turing machines are those accepted by alternating cellular automata in polynomial time for all the proposed alternating cellular automata. In particular, this is true for the weak model where the difference between existential and universal states is omitted for all the cells except the first one. It is proved that real time alternation in cellular automata is strictly more powerful than real time alternation in Turing machines, with only one read-write tape. Moreover, it is shown that in linear time uniform and weak models agree.     

K带实时图灵机计算能力与图灵机带数的关系

本文证明了对任意整数k,至少存在一个语言能被k带实时图灵机接受,但不能被(k—1)带实时图灵机所接受,从而证明了k带图灵机计算能力严格强于(k-1)带实时图灵机。     

A relationship between Turing machines and finite automata on four-dimensional input tapes

Due to the advances in computer animation, motion image processing, virtual reality systems, and so forth recently, it is useful for analyzing computation of multi-dimensional information processing to explicate the properties of four-dimensional automata. From this point of view, we first proposed four-dimensional automata in 2002, and investigated their several accepting powers. In this paper, we coutinue the study, and mainly concentrate on investigating the relationship between the accepting powers of four-dimensional finite automata and seven-way four-dimensional tape-bounded Turing Machines. This work was presented in part at the 13th International Symposium on Artificial Life and Robotics, Oita, Japan, January 31–February 2, 2008     

Unbounded-error quantum computation with small space bounds

We prove the following facts about the language recognition power of quantum Turing machines (QTMs) in the unbounded error setting: QTMs are strictly more powerful than probabilistic Turing machines for any common space bound s satisfying s(n)=o(loglogn). For “one-way” Turing machines, where the input tape head is not allowed to move left, the above result holds for s(n)=o(logn). We also give a characterization for the class of languages recognized with unbounded error by real-time quantum finite automata (QFAs) with restricted measurements. It turns out that these automata are equal in power to their probabilistic counterparts, and this fact does not change when the QFA model is augmented to allow general measurements and mixed states. Unlike the case with classical finite automata, when the QFA tape head is allowed to remain stationary in some steps, more languages become recognizable. We define and use a QTM model that generalizes the other variants introduced earlier in the study of quantum space complexity.     

Turing machines, transition systems, and interaction

This paper presents persistent Turing machines (PTMs), a new way of interpreting Turing-machine computation, based on dynamic stream semantics. A PTM is a Turing machine that performs an infinite sequence of “normal” Turing machine computations, where each such computation starts when the PTM reads an input from its input tape and ends when the PTM produces an output on its output tape. The PTM has an additional worktape, which retains its content from one computation to the next; this is what we mean by persistence.A number of results are presented for this model, including a proof that the class of PTMs is isomorphic to a general class of effective transition systems called interactive transition systems; and a proof that PTMs without persistence (amnesic PTMs) are less expressive than PTMs. As an analogue of the Church-Turing hypothesis which relates Turing machines to algorithmic computation, it is hypothesized that PTMs capture the intuitive notion of sequential interactive computation.     

Theory of one-tape linear-time Turing machines

A theory of one-tape two-way one-head off-line linear-time Turing machines is essentially different from its polynomial-time counterpart since these machines are closely related to finite state automata. This paper discusses structural-complexity issues of one-tape Turing machines of various types (deterministic, nondeterministic, reversible, alternating, probabilistic, counting, and quantum Turing machines) that halt in linear time, where the running time of a machine is defined as the length of any longest computation path. We explore structural properties of one-tape linear-time Turing machines and clarify how the machines’ resources affect their computational patterns and power.     

MINIMAL VALID AUTOMATA OF SAMPLE SEQUENCES FOR DISCRETE EVENT SYSTEMS

Minimal valid automata (MVA) refer to valid automata models that fit a given input‐output sequence sample from a Mealy machine model. They are minimal in the sense that the number of states in these automata is minimal. Critical to system identification problems of discrete event systems, MVA can be considered as a special case of the minimization problem for incompletely specified sequential machine (ISSM). While the minimization of ISSM in general is an NP‐complete problem, various approaches have been proposed to alleviate computational requirement by taking special structural properties of the ISSM at hand. In essence, MVA is to find the minimal realization of an ISSM where each state only has one subsequent state transition defined. This paper presents an algorithm that divides the minimization process into two phases: first to give a reduced machine for the equivalent sequential machine, and then to minimize the reduced machine into minimal realization solutions. An example with comprehensive coverage on how the associated minimal valid automata are derived is also included.     

One Head Machines from a symbolic approach

We consider the Turing Machine as a dynamical system and we study a particular partition projection of it. In this way, we define a language (a subshift) associated to each machine. The classical definition of Turing Machines over a one-dimensional tape is generalized to allow for a tape in the form of a Cayley Graph. We study the complexity of the language of a machine in terms of realtime recognition by putting it in relation with the structure of its tape. In this way, we find a large set of realtime subshifts some of which are proved not to be deterministic in realtime. Sofic subshifts of this class correspond to machines that cannot make arbitrarily large tours. We prove that these machines always have an ultimately periodic behavior when starting with a periodic initial configuration, and this result is proved for any Cayley Graph.