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.     

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 space bound for one-tape multidimensional Turing machines

Let L be a language recognized by a nondeterministic d-dimensional Turing machine with one worktape head of time complexity T(n). Then L can be recognized by a deterministic Turing machine of space complexity $\text{(T(n)}\text{log}\text{T(n))}{}^{\mathrm{<mtext>d</mtext><mtext>(d+1)</mtext>}}$. The proof employs a generalization of crossing sequences.     

ω-Computations on Turing machines

The paper develops the theory of Turing machines as recognizers of infinite (ω-type) input tapes. Various models of ω-type Turing acceptors are considered, varying mainly in their mechanism for recognizing ω-tapes. A comparative study of the models is made. It is shown that regardless of the ω-recognition model considered, non-deterministic ω-Turing acceptors are strictly more powerful than their deterministic counterparts. Canonical forms are obtained for each of the ω-Turing acceptor models. The corresponding families of ω-sets are studied; normal forms and algebraic characterizations are derived for each family.     

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     

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.     

Turing patterns with Turing machines: emergence and low-level structure formation

Despite having advanced a reaction–diffusion model of ordinary differential equations in his 1952 paper on morphogenesis, reflecting his interest in mathematical biology, Turing has never been considered to have approached a definition of cellular automata. However, his treatment of morphogenesis, and in particular a difficulty he identified relating to the uneven distribution of certain forms as a result of symmetry breaking, are key to connecting his theory of universal computation with his theory of biological pattern formation. Making such a connection would not overcome the particular difficulty that Turing was concerned about, which has in any case been resolved in biology. But instead the approach developed here captures Turing’s initial concern and provides a low-level solution to a more general question by way of the concept of algorithmic probability, thus bridging two of his most important contributions to science: Turing pattern formation and universal computation. I will provide experimental results of one-dimensional patterns using this approach, with no loss of generality to a n-dimensional pattern generalisation.     

Computing with words via Turing machines: a formal approach

Computing with words (CW) as a methodology, means computing and reasoning by the use of words in place of numbers or symbols, which may conform more to humans' perception when describing real-world problems. In this paper, as a continuation of a previous paper, we aim to develop and deepen a formal aspect of CW. According to the previous paper, the basic point of departure is that CW treats certain formal modes of computation with strings of fuzzy subsets instead of symbols as their inputs. Specifically, 1) we elaborate on CW via Turing machine (TM) models, showing the time complexity is at least exponential if the inputs are strings of words; 2) a negative result of (6) not holding is verified which indicates that the extension principle for CW via TMs needs to be re-examined; 3) we discuss CW via context- free grammars and regular grammars and the extension principles for CW via these formal grammars are set up; 4) some equivalences between fuzzy pushdown automata (respectively, fuzzy finite-state automata) fuzzy context-free grammars (respectively, fuzzy regular grammars) are demonstrated in the sense that the inputs are instead strings of words; 5) some instances are described in detail. Summarily formal aspect of CW is more systematically established more deeply dealt with while some new problems also emerge.     

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.     

Output concepts for accelerated Turing machines

The accelerated Turing machine (ATM) is the work-horse of hypercomputation. In certain cases, a machine having run through a countably infinite number of steps is supposed to have decided some interesting question such as the Twin Prime conjecture. One is, however, careful to avoid unnecessary discussion of either the possible actual use by such a machine of an infinite amount of space, or the difficulty (even if only a finite amount of space is used) of defining an outcome for machines acting like Thomson’s lamp. It is the authors’ impression that insufficient attention has been paid to introducing a clearly defined counterpart for ATMs of the halting/non-halting dichotomy for classical Turing computation. This paper tackles the problem of defining the output, or final message, of a machine which has run for a countably infinite number of steps. Non-standard integers appear quite useful in this regard and we describe several models of computation using filters.     

A note on deterministic three-way tape-bounded two-dimensional Turing machines

In this paper, we first investigate the relationship between the accepting powers of four-way two-dimensional finite automata and deterministic three-way tape-bounded two-dimensional Turing machines whose input tapes are restricted to square ones. The second part of this paper solves several open problems concerning closure properties of deterministic three-way tape-bounded two-dimensional Turing machines.     

The time-precision tradeoff problem on on-line probabilistic Turing machines

A probabilistic Turing machine (PTM) is a Turing machine that flips an unbiased coin to decide its next movement and solves a problem with some error probability. It is expected that PTMs need more time if a smaller error probability is required. This is a sort of time-precision tradeoff and is shown to occur actually on on-line probabilistic Turing machine acceptors (ONPTMs). That is, we show the existence of a set such that it is recognized by an ONPTM with $\text{1}\text{2}\text{-(}\text{log}\text{n)/}\text{8}\text{n}$ bounded error probability in O(n) time but for every $\text{ε, 0<ε<}\text{1}\text{2}$, it requires more than O((n/log n)²) time to recognize this set with bounded error probability by ONPTMs. Moreover our result is also shown to be an example of difference between nondeterministic computations and probabilistic ones.     

Abstract geometrical computation 4: Small Turing universal signal machines

This paper provides several very small signal machines able to perform any computation—in the classical understanding—generated from Turing machines, cellular automata and cyclic tag systems. A halting universal signal machine with 13 meta-signals and 21 collision rules is presented (resp. 15 and 24 for a robust version). If infinitely many signals are allowed to be present in the initial configuration, five meta-signals and seven collision rules are enough to achieve non-halting weak universality (resp. six and nine for a robust version).     

The complexity of small universal Turing machines: A survey

We survey some work concerned with small universal Turing machines, cellular automata, tag systems, and other simple models of computation. For example, it has been an open question for some time as to whether the smallest known universal Turing machines of Minsky, Rogozhin, Baiocchi and Kudlek are efficient (polynomial time) simulators of Turing machines. These are some of the most intuitively simple computational devices and previously the best known simulations were exponentially slow. We discuss recent work that shows that these machines are indeed efficient simulators. As a related result, we also find that Rule 110, a well-known elementary cellular automaton, is also efficiently universal. We also review a large number of old and new universal program size results, including new small universal Turing machines and new weakly, and semi-weakly, universal Turing machines. We then discuss some ideas for future work arising out of these, and other, results.     

On the power of alternation on reversal-bounded alternating Turing machines with a restriction

Whether or not there is a difference of the power among alternating Turing machines with a bounded number of alternations is one of the most important problems in the field of computer science. This paper presents the following result: Let R(n) be a space and reversal constructible function. Then, for any k 1, we obtain that the class of languages accepted by off-line 1-tape rσ_k machines running in reversal O(R(n)) is equal to the class of languages accepted by off-line 1-tape σ₁ machines running in reversal O(R(n)). An off-line 1-tape σ_k machine M is called an off-line 1-tape rσ_k machine if M always limits the non-blank part of the work-tape to at most O(R(n) log n) when making an alternation between universal and existential states during the computation.