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     

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.     

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     

Probabilistic rebound Turing machines

This paper introduces a probabilistic rebound Turing machine (PRTM), and investigates the fundamental property of the machine. We first prove a sublogarithmic lower space bound on the space complexity of this model with bounded errors for recognizing specific languages. This lower bound strengthens a previous lower bound for conventional probabilistic Turing machines with bounded errors. We then show, by using our lower space bound and an idea in the proof of it, that

Full-size image

where £[PRTM(o(logn))] denotes the class of languages recognized by o(logn) space-bounded PRTMs with error probability less than . Furthermore, we show that there is an infinite space hierarchy for £[PRTM(o(logn))]. We finally show that £[PRTM(o(logn))] is not closed under concatenation, Kleene +, and length-preserving homomorphism. This paper answers two open problems in a previous paper.     

A note on the ‘parallel computation thesis’

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

Three-dimensional multiinkdot automata

Recently, related to the open problem whether deterministic and nondeterministic space (especially lower-level) complexity classes are separated, inkdot Turing machines were introduced. On the other hand, due to the advances in many application areas about three-dimensional information processing, the research on three-dimensional automata as the computation of three-dimensional pattern processing has been meaningful. From this viewpoint, we propose a three-dimensional multiinkdot automata, and investigate some properties of three-dimensional multiinkdot automata.This work was presented, in part, at the 9th International Symposium on Artificial Life and Robotics, Oita, Japan, January 28–30, 2004     

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.     

Simulating reversible Turing machines and cyclic tag systems by one-dimensional reversible cellular automata

In this paper, we investigate how 1-D reversible cellular automata (RCAs) can simulate reversible Turing machines (RTMs) and cyclic tag systems (CTSs). A CTS is a universal string rewriting system proposed by M. Cook. First, we show that for any m-state n-symbol RTM there is a 1-D 2-neighbor RCA with a number of states less than (m+2n+1)(m+n+1) that simulates it. It improves past results both in the number of states and in the neighborhood size. Second, we study the problem of finding a 1-D RCA with a small number of states that can simulate any CTS. So far, a 30-state RCA that can simulate any CTS and works on ultimately periodic infinite configurations has been given by K. Morita. Here, we show there is a 24-state 2-neighbor RCA with this property.     

Some properties of four-dimensional multicounter automata

Recently, due to the advances in many application areas such as computer animation, motion image processing, and so forth, it has become increasingly apparent that the study of four-dimensional pattern processing is of crucial importance. Thus, we think that research into four-dimensional automata as a computational model of four-dimensional pattern processing is also meaningful. This article introduces four-dimensional multicounter automata, and investigates some of their properties. We show the differences between the accepting powers of seven-way and eight-way four-dimensional multicounter automata, and between the accepting powers of deterministic and nondeterministic seven-way four-dimensional multicounter automata. This work was presented in part at the 10th International Symposium on Artificial Life and Robotics, Oita, Japan, February 4–6, 2005     

Approximation and universality of fuzzy Turing machines

Fuzzy Turing machines are the formal models of fuzzy algorithms or fuzzy computations. In this paper we give several different formulations of fuzzy Turing machine, which correspond to nondeterministic fuzzy Turing machine using max-＊ composition for some t-norm＊ （or NFTM＊, for short）, nondeterministic fuzzy Turing machine （or NFTM）, deterministic fuzzy Turing machine （or DFTM）, and multi-tape versions of fuzzy Turing machines. Some distinct results compared to those of ordinary Turing machines are obtained. First, it is shown that NFTM＊, NFTM, and DFTM are not necessarily equivalent in the power of recognizing fuzzy languages if the t-norm＊ does not satisfy finite generated condition, but are equivalent in the approximation sense. That is to say, we can approximate an NFTM＊ by some NFTM with any given accuracy; the related constructions are also presented. The level characterization of fuzzy recursively enumerable languages and fuzzy recursive languages are exploited by ordinary r.e. languages and recursive languages. Second, we show that universal fuzzy Turing machine exists in the approximated sense. There is a universal fuzzy Turing machine that can simulate any NFTM＊ on it with a given accuracy.     

Transcending Turing Computability

It has been argued that neural networks and other forms of analog computation may transcend the limits of Turing-machine computation; proofs have been offered on both sides, subject to differing assumptions. In this article I argue that the important comparisons between the two models of computation are not so much mathematical as epistemological. The Turing-machine model makes assumptions about information representation and processing that are badly matched to the realities of natural computation (information representation and processing in or inspired by natural systems). This points to the need for new models of computation addressing issues orthogonal to those that have occupied the traditional theory of computation.     

Space-bounded simulation of multitape turing machines

A new proof of a theorem of Hopcroft, Paul, and Valiant is presented: Every deterministic multitape Turing machine of time complexityT(n) can be simulated by a deterministic Turing machine of space complexityT(n)/logT(n). The proof includes an overlap argument.Supported by National Science Foundation Grant No. MCS-78-04343.Supported by National Science Foundation Grant No. MCS-77-19754 and the Fannie and John Hertz Foundation.     

The Turing way to parameterized complexity

We propose a general proof technique based on the Turing machine halting problem that allows us to establish membership results for the classes W[1], W[2], and W[P]. Using this technique, we prove that Perfect Code belongs to W[1], Steiner Tree belongs to W[2], and α-Balanced Separator, Maximal Irredundant Set, and Bounded DFA Intersection belong to W[P].     

A Turing machine time hierarchy

The time separation results concerning classes of languages over a single-letter alphabet accepted by multi-tape nondeterministic Turing machines, well-known from Seiferas, Fischer and Meyer (1978), are supplemented. Moreover, via a universal machine a modified time complexity measure UTIME of Turing machines computations which is sensitive to multiplication by constants (i.e., UTIME(t) ? UTIME(kt), where UTIME(t) is the class of languages of complexity not larger than t) is introduced. On the level of this measure, the results concerning languages over one- and two-letter alphabets are refined. The proof tools are versions of a translational diagonalization and of an unpadding technique.     

Pyramidal thinning algorithm for SIMD parallel machines

We propose a parallel thinning algorithm for binary pictures. Given an N × N binary image including an object, our algorithm computes in O(N²) the skeleton of the object, using a pyramidal decomposition of the picture. The behavior of this algorithm is studied considering a family of digitalization of the same object at a different level of resolution. With the Exclusive Read Exclusive Write (EREW) Parallel Random Access Machine (PRAM), our algorithm runs in O(log N) time using O(N²/logN) processors and it is work-optimal. The same result is obtained with high-connectivity distributed memory SIMD machines having strong hypercube and pyramid. We describe the basic operator, the pyramidal algorithm and some experimental results on the SIMD MasPar parallel machine.     

Speed-Up Theorems in Type-2 Computations Using Oracle Turing Machines

A classic result known as the speed-up theorem in machine-independent complexity theory shows that there exist some computable functions that do not have best programs for them (Blum in J. ACM 14(2):322–336, 1967 and J. ACM 18(2):290–305, 1971). In this paper we lift this result into type-2 computations. Although the speed-up phenomenon is essentially inherited from type-1 computations, we observe that a direct application of the original proof to our type-2 speed-up theorem is problematic because the oracle queries can interfere with the speed of the programs and hence the cancellation strategy used in the original proof is no longer correct at type-2. We also argue that a type-2 analog of the operator speed-up theorem (Meyer and Fischer in J. Symb. Log. 37:55–68, 1972) does not hold, which suggests that this curious speed-up phenomenon disappears in higher-typed computations beyond type-2. The result of this paper adds one more piece of evidence to support the general type-2 complexity theory under the framework proposed in Li (Proceedings of the Third International Conference on Theoretical Computer Science, pp. 471–484, 2004 and Proceedings of Computability in Europe: Logical Approach to Computational Barriers, pp. 182–192, 2006) and Li and Royer (On type-2 complexity classes: Preliminary report, pp. 123–138, 2001) as a reasonable setup.     

Large parallel machines can be extremely slow for small problems

We consider concurrent-write PRAMs with a large number of processors of unlimited computational power and an infinite shared memory. Our adversary chooses a small number of our processors and gives them a 0–1 input sequence (each chosen processor gets a bit, and each bit is given to one processor). The chosen processors are required to compute thePARITY of their input, while the others do not take part in the computation. Ifat most q processors are chosen andq 1/2 log logn, then we show that computing PARITY needsq steps in the worst case. On the other hand, there exists an algorithm which computes PARITY inq steps (for anyq <n) in this model, thus our result is sharp. Surprisingly, if our adversary choosesexactly q of our processors, then they can compute PARITY in [q/2] + 2 steps, and in this case we show that it needs at least [q2] steps. Our result implies that large parallel machines which are efficient when only a small number of their processors are active cannot be constructed. On the other hand, a result of Ajtai and Ben-Or [1] shows that if we haven input bits which contain at most polylogn 1's and polynomially many processors which are all allowed to work, then thePARITY can be solved inconstant time.