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     

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.     

A note on alternating one-pebble Turing machines with sublogarithmic space

Inoue et al. [A. Inoue, A. Ito, K. Inoue, T. Okazaki, Some properties of one-pebble Turing machines with sublogarithmic space, Theoret. Comput. Sci. 341 (2005) 138-149] conjectured that the language {ww|w∈⁺{a,b}} is not accepted by any alternating one-pebble Turing machine with sublogarithmic space. In this paper we disprove the conjecture by showing that there exists an alternating one-pebble Turing machine accepting the language in loglogn space.     

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     

Element distinctness on one-tape Turing machines: a complete solution

We give a complete characterization of the complexity of the element distinctness problem for n elements of bits each on deterministic and nondeterministic one-tape Turing machines. We present an algorithm running in time for deterministic machines and nondeterministic solutions that are of time complexity . For elements of logarithmic size , on nondeterministic machines, these results close the gap between the known lower bound and the previous upper bound . Additional lower bounds are given to show that the upper bounds are optimal for all other possible relations between m and n. The upper bounds employ hashing techniques, while the lower bounds make use of the communication complexity of set disjointness.Received: 23 April 2001, Published online: 2 September 2003Holger Petersen: Supported by Deutsche Akademie der Naturforscher Leopoldina, grant number BMBF-LPD 9901/8-1 of Bundesministerium für Bildung und Forschung.     

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).     

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     

Matching upper and lower bounds for simulations of several linear tapes on one multidimensional tape

We prove an O(t(n) ^d (t(n)) ^? / log t(n)) time bound for the sim-ulation of t(n) steps of a Turing machine using several one-dimensional work tapes on a Turing machine using one d-dimensional work tape, . We prove a matching lower bound which holds for the problem of recognizing languages on machines with a separate one-way input tape. Received: March 1995.     

Bridging across the log(n) Space Frontier

This paper establishes the importance of even the lowest possible level of space bounded computations. We show that DLOG does not coincide with NLOG if and only if there exists a tally set in NSPACE(log log n)\DSPACE(log log n). This result stands in perfect analogy to the related results concerning linear space or exponential time. Moreover, the above problem is equivalent to the existence of a functions(n), with arbitrarily slow or rapid growth rate, that is nondeterministically fully space constructible but cannot be constructed deterministically. We also present a “hardest” fully space constructibles(n)∈O(log log n), a functional counterpart of log-space complete languages. These nonrelativized results are obtained by the use of oracle machines consuming much larger amount of space, in range betweennand 2^d·n.     

Perfect computational equivalence between quantum Turing machines and finitely generated uniform quantum circuit families

In order to establish the computational equivalence between quantum Turing machines (QTMs) and quantum circuit families (QCFs) using Yao’s quantum circuit simulation of QTMs, we previously introduced the class of uniform QCFs based on an infinite set of elementary gates, which has been shown to be computationally equivalent to the polynomial-time QTMs (with appropriate restriction of amplitudes) up to bounded error simulation. This result implies that the complexity class BQP introduced by Bernstein and Vazirani for QTMs equals its counterpart for uniform QCFs. However, the complexity classes ZQP and EQP for QTMs do not appear to equal their counterparts for uniform QCFs. In this paper, we introduce a subclass of uniform QCFs, the finitely generated uniform QCFs, based on finite number of elementary gates and show that the class of finitely generated uniform QCFs is perfectly equivalent to the class of polynomial-time QTMs; they can exactly simulate each other. This naturally implies that BQP as well as ZQP and EQP equal the corresponding complexity classes of the finitely generated uniform QCFs.     

A note on the ‘parallel computation thesis’

We prove that in some sense the ‘parallel computation thesis’ is wrong.     

基于图灵模型的P=？ NP问题分析

P=？NP问题是计算复杂性中的核心问题。2000年,美国克雷实验室将其收录为“千禧年大奖”七个问题之首。本文基于图灵模型,对P=？NP问题的研究现状、P=NP／P≠NP 证明方法、NPC问题求解方法及研究进展进行阐述。     

Simulation of simultaneous safe recursion over an arbitrary structure

In [O. Bournez, F. Cucker, P.J. de Naurois, J.Y. Marion, Computability over an arbitrary structure. Sequential and parallel polynomial time, in: Lecture Notes in Computer Science, vol. 2620, Springer, Berlin, 2003, pp. 185-199] the class of safe recursive functions over an arbitrary structure is defined. A question of simulation of the simultaneous safe recursion by single safe recursion was set. We prove that this simulation is feasible using bounded coding and decoding functions.     

Kolmogorov Complexity for Possibly Infinite Computations

In this paper we study the Kolmogorov complexity for non-effective computations, that is, either halting or non-halting computations on Turing machines. This complexity function is defined as the length of the shortest input that produce a desired output via a possibly non-halting computation. Clearly this function gives a lower bound of the classical Kolmogorov complexity. In particular, if the machine is allowed to overwrite its output, this complexity coincides with the classical Kolmogorov complexity for halting computations relative to the first jump of the halting problem. However, on machines that cannot erase their output –called monotone machines–, we prove that our complexity for non effective computations and the classical Kolmogorov complexity separate as much as we want. We also consider the prefix-free complexity for possibly infinite computations. We study several properties of the graph of these complexity functions and specially their oscillations with respect to the complexities for effective computations.