Search

The paper focuses on the relation between biological and computational information processing. Several simple biological operations, as the exchange of molecules via cellular membrane or the cellular growth and separation, are abstracted into a mathematical model called membrane system (P system). This paper studies tissue P systems where a fixed interaction graph defines the communication between various types of cells. Polynomially uniform families of tissue P systems with the operation of cell separation were recently studied. Their computational power in polynomial time was shown to range between P and NP ∪ co - NP , characterizing borderlines between tractability and intractability by the length of rules controlling the interchange of objects. Here, we show that the computational power of these uniform families is limited by the class PSPACE , which is the class characterizing the power of classical parallel computing models, such as PRAM or the alternating Turing machine.

This paper investigates a relationship among the accepting powers of deterministic, nondeterministic, and alternating one-pebble two-dimensional Turing machines, and shows that (i) nondeterminism are more powerful than determinism for o(log n) space-bounded one-pebble two-dimensional Turing machines whose input tapes are restricted to square ones, and (ii) alternation are more powerful than nondeterminism for f(m)+g(n) (resp., f(m) × g(n)) space-bounded one-pebble two-dimensional Turing machines, where f : N → N is an arbitrary monotonic nondecreasing funcion space-constractible by a deterministic one-pebble two-dimensional Turing machine, and g : N → N is an arbitrary function such that g(n) = o(log n) (resp., g(n) = o(log n/loglog n)).

This paper introduces two-dimensional probabilistic Turing machines (2-ptm's), and investigates several properties of them. We first investigate a relationship between two-dimensional alternating finite automata (2-afa's) and 2-ptm's with error probability less than 1 2 and with sublogarithmic space, and show that there is a set of square tapes accepted by 2-afa, but not recognized by any o(log-n) space-bounded 2-ptm with error probability less than 1 2 . This partially solves an open problem in Okazaki et al. (Inform. Sci., to appear). We next investigate a space hierarchy of 2-ptm's with error probability less than 1 2 and with sublogarithmic space, and show that if L(n) is space-constructible by a two-dimensional Turing machine, there is a set of square tapes accepted by a strongly L(n) space-bounded two-dimensional deterministic Turing machine, but not recognized by any L(n) space-bounded 2-ptm with error probability less than 1 2 .

We investigate several properties of three-dimensional alternating Turing machines whose input tapes are restricted to cubic ones. We first investigate the relationship between the classes of sets accepted by space-bounded and finitely leaf-size bounded five-way three-dimensional alternating Turing machines and the classes of sets which are finite intersections of sets accepted by space-bounded five-way three-dimensional nondeterministic Turing machines. Then, we investigate the accepting powers of three-dimensional alternating Turing machines with only universal states.

This paper deals with the accepting powers of five-way three-dimensional alternating machines and six-way three-dimensional alternating machines whose input tapes are restricted to cubic ones. We first show that for space smaller than log m , five-way three-dimensional alternating Turing machines are less powerful than six-way three-dimensional alternating Turing machines. We then show that the set of all the three-dimensional connected tapes can be accepted by a six-way three-dimensional alternating finite automaton, but not accepted by any o (log m ) space-bounded five-way three-dimensional alternating Turing machine. Finally, we show that there exists a language accepted by a five-way three-dimensional alternating finite automaton, but not accepted by any o (log m ) space-bounded six-way three-dimensional nondeterministic Turing machine.

We investigate the properties of three-way two-dimensional alternating Turing machines (TR2-ATMs), which are restricted versions of ordinary four-way two-dimensional alternating Turing machines (2-ATMs). We first show that 2-ATMs are more powerful than TR2-ATMs with spaces below log m . Then, we investigate the closure properties of TR2-ATMs on square and general rectangular input tapes. Finally, we show that o (log m ) space-bounded TR2-ATMs cannot accept the set of all square connected pictures.

This paper investigates closure properties (under row and column catenations, row and column closures, row and column cyclic closures, and projection) of the classes of sets accepted by four-way and three-way tape-bounded two-dimensional Turing machines whose input tapes are not restricted to square ones.

This paper investigates a space hierarchy of the classes of sets accepted by alternating space-bounded two-dimensional Turing machines which have only universal states and whose input tapes are restricted to square ones and shows that there exists a dense hierarchy for the classes of sets accepted by these Turing machines with spaces of size less than or equal to log m.

The standard way of assigning complexity to a one-tape Turing machine, by the state-symbol product, is clearly inadequate for machines with more than one tape. Letting an (m,n,p)-machine be a Turing machine with m states, n symbols (including any end markers), and p tapes, the number m· np gives the maximum number of operating rules for an (m,n,p)-machine and serves as a fairly reasonable complexity criterion, reducing to the state-symbol product when p = 1. A (2,3,2)-machine has been designed to simulate an arbitrary tag system with deletion number 2, and therefore is universal [1]. Also a (1,2,4)-machine, having a fixed loop for one of its four tapes, has been designed ; this machine is universal by its ability to simulate an arbitrary “B machine” (6). Under the criterion stated above, these machines have complexities of 18 and 16, respectively, both less than any reported state-symbol product. Moreover, any (m,n,p)-machine may be simulated, step-by-step, by a (1,2,p′)-machine, where p′ = p⌜log 2 (n)⌝ + ⌜log 2 (m)⌝ . If the logarithms are integral, this transformation is realized with no increase in complexity. However, since the full power of the additional tapes is not utilized in this transformation, it appears that this complexity criterion does not provide a severe enough penalty for the introduction of additional tapes to a Turing machine.

The study of computational complexity is continued under the additional requirement that the Turing machines operate in real time. The work reported here is motivated by that of Rabin [I] which asks implicitly about the computational power of n tape vs. n+1 tape real time Turing machines and that of Hartmanis [2], who attempts a complexity measure for Turing machines in terms of reversals. The first result concerns itself with n tape real time Turing machines operating in a reversal bounded mode. A doubly infinite hierarchy (tapes-reversals) of classes of real time computable functions is shown to exist. The second result deals with n deterministic real time pushdown automata operating independently in parallel. It is shown that an increase in the number of pushdown automata operating in this manner always yields an increase in the computational power of the configuration.

TUTOR is a high speed Turing machine simulator, written in IBM System 360 Assembler Language. Turing machines are represented by flow diagrams using H. Hernes table of machines as the basic elements. Composite machines so represented may themselves be used as elements of other machines, thus incorporating the concept of subroutines. In this paper the relationship of a flow diagram to the basic concept of a Turing machine is developed, the functions of the basic machines are described, and a complete programmer's guide is included.