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.     

Bounds for the Element Distinctness Problem on one-tape Turing machines

We disprove a conjecture of López-Ortiz by showing that the Element Distinctness Problem for n numbers of size O(logn) can be solved in O(n²(logn)^3/2(loglogn)^1/2) steps by a nondeterministic one-tape Turing machine. Further we give a simplified algorithm for solving the problem for shorter numbers in time O(n²logn) on a deterministic one-tape Turing machine and a new proof of the matching lower bound.     

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     

A note on the ‘parallel computation thesis’

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

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.     

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.     

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.     

基于图灵机的递归技术的实现陈晓亮[1] 卢朝辉[2] 宋文[1]

图灵机是通用的计算机模型,一般程序设计和以图灵机为机器模型的计算也是支持递归的。本文首先分析了递归的特征,利用多带图灵机作为计算模型,定义了递归技术转移 函数形式,提出了图灵机递归过程信息传递与保存的方法,给出了图灵机调用的实现,继而给出了图灵机递归技术的实现,同时证明了图灵机的调用与图灵机的递归调用是图灵可识别的。     

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.