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.     

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.     

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     

On parallel Turing machines with multi-head control units

This paper deals with parallel Turing machines with multi-head control units on one or more tapes which can be considered as a generalization of cellular automata. We discuss the problem of finding an appropriate measure of space complexity. A definition is suggested which implies that the model is in the first machine class. It is shown that without loss of generality it suffices to consider only parallel Turing machines of certain normal forms.     

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.     

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

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.     

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.     

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.     

Turing machines with access to history

We study remembering Turing machines, that is Turing machines with the capability to access freely the history of their computations. These devices can detect in one step via the oracle mechanism whether the storage tapes have exactly the same contents at the moment of inquiry as at some past moment in the computation. The s(n)-space-bounded remembering Turing machines are shown to be able to recognize exactly the languages in the time-complexity class determined by bounds exponential in s(n). This is proved for deterministic, non-deterministic, and alternating Turing machines.     

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.     

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.     

Some properties of four-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: a storage tape and an 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 7 years or so, automata on a four-dimensional tape have been proposed as computational models of four-dimensional pattern processing, and several properties of such automata have been obtained. We proposed a four-dimensional parallel Turing machine (4-PTM), and dealt with a hardware-bounded 4-PTM in which each side-length of each input tape is equivalent. We believe that this machine is useful in measuring the parallel computational complexity of three-dimensional images. In this work, we continued the study of the 3-PTM, in which each side-length of each input tape is equivalent, and investigated some of its accepting powers.     

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     

Simplicity via provability for universal prefix-free Turing machines

Universality, provability and simplicity are key notions in computability theory. There are various criteria of simplicity for universal Turing machines. Probably the most popular one is to count the number of states/symbols. This criterion is more complex than it may appear at a first glance. In this note we propose three new criteria of simplicity for universal prefix-free Turing machines. These criteria refer to the possibility of proving various natural properties of such a machine (its universality, for example) in a formal theory, Peano arithmetic or Zermelo–Fraenkel set theory. In all cases some, but not all, machines are simple.