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.     

The complexity of on-line simulations between multidimensional turing machines and random access machines

To study different implementations of arrays, we present four results on the time complexities of on-line simulations between multidimensional Turing machines and random access machines (RAMs). First, everyd-dimensional Turing machine of time complexityt can be simulated by a log-cost RAM running inO(t(logt)^1–(1/d)(log logt)^1/d) time. Second, everyd-dimensional Turing machine of time complexityt can be simulated by a unit-cost RAM running inO(t/(logt)^1/d) time, provided that the input length iso(t/(logt)^1/d). Third, there is a log-cost RAMR of time complexityO(n), wheren is the input length, such that, for anyd-dimensional Turing machineM that simulatesR on-line,M requires (n ^{1 + (1/d)})/(logn(log logn)^{1 + (1/d)})) time. Fourth, every unit-cost RAM of time complexityt can be simulated by ad-dimensional Turing machine inO(t ²(logt)^1/2) time ifd = 2, and inO(t ²) time ifd 3. This result uses the weight-balanced trees of Nievergelt and Reingold.This paper was prepared while M. C. Loui was visiting the National Science Foundation in Washington, DC, and the Institute for Advanced Computer Studies, University of Maryland, College Park, MD. The views, opinions, and conclusions in this paper are those of the authors and should not be construed as an official position of the National Science Foundation, Department of Defense, U.S. Air Force, or any other U.S. government agency. The research of M. C. Loui was supported by the National Science Foundation under Grant CCR-8922008.     

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.     

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.     

The Computational Complexity of Some Julia Sets

Numerous computer programs have been written to compute sets of points which approximate Julia sets [4]. Usually, no error estimations are added so that it remains unclear, how good such approximations are. Furthermore, high precision pictures are unreliable because of rounding errors, since the realizing computer programs use fixed length floating point numbers. Computable error estimation w.r.t. the Hausdorff metric d_H means that the set is recursive [10]. Many Julia sets J are recursive [11]. Recursive compact subsets of the Euclidean plane have a computable Turing machine time complexity [10]. In this paper we prove that the Julia set of a complex function f(z) = z² + c for c < 1/4 can be computed locally in time O(k²M(k)) (where M(k) is a time bound for multiplication of k-bit integers). Roughly speaking, the local time complexity is the number of Turing machine steps to decide for a single point whether it belongs to a grid K_k (2^−k · )² such that d_H(K_k,J) ≤ = 2^−k.     

Improved Bounds for Functions Related to Busy Beavers

Consider Turing machines that use a tape infinite in both directions, with the tape alphabet {0,1} . Rado's busy beaver function, ones(n), is the maximum number of 1's such a machine, with n states, started on a blank (all-zero) tape, may leave on its tape when it halts. The function ones(n) is non-computable; in fact, it grows faster than any computable function. Other functions with a similar nature can be defined also. All involve machines of n states, started on a blank tape. The function time(n) is the maximum number of moves such a machine may make before halting. The function num(n) is the largest number of 1's such a machine may leave on its tape in the form of a single run; and the function space(n) is the maximum number of tape squares such a machine may scan before it halts. This paper establishes new bounds on these functions in terms of each other. Specifically, we bound time(n) by num(n+o(n)), improving on the previously known bound num(3n+6) . This result is obtained using a kind of ``self-interpreting' Turing machine. We also improve on the trivial relation space(n) ≤ time(n) , using a technique of counting crossing sequences. Received July 18, 2000, and in revised form October 10, 2001. Online publication February 20, 2002.     

Classically-controlled Quantum Computation

It is reasonable to assume that quantum computations take place under the control of the classical world. For modelling this standard situation, we introduce a Classically-controlled Quantum Turing Machine (CQTM) which is a Turing machine with a quantum tape for acting on quantum data, and a classical transition function for a formalized classical control. In CQTM, unitary transformations and quantum measurements are allowed. We show that any classical Turing machine is simulated by a CQTM without loss of efficiency. Furthermore, we show that any k-tape CQTM is simulated by a 2-tape CQTM with a quadratic loss of efficiency. The gap between classical and quantum computations which was already pointed out in the framework of measurement-based quantum computation (see [S. Perdrix, Ph. Jorrand, Measurement-Based Quantum Turing Machines and their Universality, arXiv, quant-ph/0404146, 2004]) is confirmed in the general case of classically-controlled quantum computation. In order to appreciate the similarity between programming classical Turing machines and programming CQTM, some examples of CQTM will be given in the full version of the paper. Proofs of lemmas and theorems are omitted in this extended abstract.     

Simulations among multidimensional turing machines

For all d ? 1 and all e >d, every deterministic multihead e-dimensional Turing machine of time complexity T(n) can be simulated on-line by a deterministic multihead d-dimensional Turing machine in time O(T(n)^1+1?d?1?(logT(n))⁰⁽¹⁾). This simulation almost achieves the known lower bound $\text{Ω(T(n)}{}^{\mathrm{1+1?}}\text{d?1?e)}$ on the time required. The simulation is interpreted in terms of dynamic embeddings among arrays with local access.     

Comparing Verboseness for Finite Automata and Turing Machines

A language is called (m,n)-verbose if there exists a Turing machine that enumerates for any n words at most m possibilities for their characteristic string. This notion is compared with (m,n)-fa-verboseness, where instead of a Turing machine a finite automaton is used. By use of a new diagonalisation method, where finite automata trick Turing machines, it is shown that all (m,n)-verbose languages are (h,k)-verbose iff all (m,n)-fa-verbose languages are (h,k)-fa-verbose. In other words, Turing machines and finite automata behave exactly the same way with respect to inclusion of verboseness classes. This identical behaviour implies that the nonspeedup theorem also holds for finite automata. As an application of the theoretical framework, a lower bound is derived on the number of bits that need to be communicated to finite automata protocol checkers for nonregular protocols.     

On non-determinancy in simple computing devices

Summary This paper studies one-tape Turing machines with k read-only heads which are restricted to the original input. The main result shows that if any set accepted by such a 3-head non-deterministic Turing machine can be accepted by a deterministic Turing machine with more read-only heads, then the deterministic and non-deterministic context-sensitive languages are identical. Several related results are derived and some tantalizing open problems are discussed.This research has been supported in part by National Science Foundation Grant GJ-155.     

On two-tape real-time computation and queues

A Turing machine with two storage tapes cannot simulate a queue in both real-time and with at least one storage tape head always within o(n) squares from the start square. This fact may be useful for showing that a two-head tape unit is more powerful in real-time than two one-head tape units, as is commonly conjectured.     

Real-time solutions of the origin-crossing problem

Then-dimensional origin-crossing language,O _n, is a language each of whose words describes a walk throughn-dimensional space beginning and ending at the origin. For eachn, O _n is real-time recognizable by ann-counter machine but not by any (n — 1)-counter machine. In contrast, for alln, O _n is real-time recognizable by a one-tape Turing machine.     

K带实时图灵机计算能力与图灵机带数的关系

本文证明了对任意整数k,至少存在一个语言能被k带实时图灵机接受,但不能被(k—1)带实时图灵机所接受,从而证明了k带图灵机计算能力严格强于(k-1)带实时图灵机。     

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 note on busy beavers and other creatures

Consider Turing machines that read and write the symbols 1 and 0 on a one-dimensional tape that is infinite in both directions, and halt when started on a tape containing all O's. Rado'sbusy beaver function ones(n) is the maximum number of 1's such a machine, withn states, may leave on its tape when it halts. The function ones(n) is noncomputable; in fact, it grows faster than any computable function. Other functions with a similar nature can also be defined. The function time(n) is the maximum number of moves such a machine may make before halting. The function num(n) is the largest number of 1's such a machine may leave on its tape in the form of a single run; and the function space(n) is the maximum number of tape squares such a machine may scan before it halts. This paper establishes a variety of bounds on these functions in terms of each other; for example, time(n) ≤ (2n − 1) × ones(3n + 3). In general, we compare the growth rates of such functions, and discuss the problem of characterizing their growth behavior in a more precise way than that given by Rado.     

One way finite visit automata

A one-way preset Turing machine with base L is a nondeterministic on-line Turing machine with one working tape preset to a member of L. FINITEREVERSAL($\text{L}$) (FINITEVISIT ($\text{L}$)) is the class of languages accepted by one-way preset Turing machines with bases in $\text{L}$ which are limited to a finite number of reversals (visits). For any full semiAFL $\text{L}$, FINITEREVERSAL ($\text{L}$) is the closure of $\text{L}$ under homomorphic replication or, equivalently, the closure of $\text{L}$ under iteration of controls on linear context-free grammars while FINITEVISIT ($\text{L}$) is the result of applying controls from $\text{L}$ to absolutely parallel grammars or, equivalently, the closure of $\text{L}$ under deterministic two-way finite state transductions. If $\text{L}$ is a full AFL with $\text{L}$ ≠ FINITEVISIT($\text{L}$), then FINITEREVERSAL($\text{L}$) ≠ FINITEVISIT($\text{L}$). In particular, for one-way checking automata, k + 1 reversals are more powerful than k reversals, k + 1 visits are more powerful than k visits, k visits and k + 1 reversals are incomparable and there are languages definable within 3 visits but no finite number of reversals. Finite visit one-way checking automaton languages can be accepted by nondeterministic multitape Turing machines in space log₂n. Results on finite visit checking automata provide another proof that not all context-free languages can be accepted by one-way nonerasing stack automata.     

On time versus space II

Every t(n)-time bounded RAM (assuming the logarithmic cost measure) can be simulated by a t(n)/log t(n)-space bounded Turing machine and every t(n)-time bounded Turing machine with d-dimensional tapes by a bounded machine, where n is the length of the input. A class $\text{E}$ of storage structures which generalizes multidimensional tapes is defined. Every t(n)-time bounded Turing machine whose storage structures are in $\text{E}$ can be simulated by a t(n) loglog t(n)/log t(n)-space bounded Turing machine.     

A Note on Maxwell's Demon and Universal Computation

Abstract

An analogy between a Maxwellian Demon capable of regulating the passage of particles between two chambers and a Turing machine capable of manipulating a tape and its symbols, is made explicit. It is shown that a slightly modified Maxwell's Demon can simulate a Universal Turing Machine.     

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     

On alternation

Summary Every alternating t(n)-time bounded multitape Turing machine can be simulated by an alternating t(n)-time bounded 1-tape Turing machine. Every nondeterministic t(n)-time bounded 1-tape Turing machine can be simulated by an alternating (n + (t(n)) ^1/2)-timebounded 1-tape Turing machine. For wellbehaved functions t(n) every nondeterministic t(n)-time bounded 1-tape Turing machine can be simulated by a deterministic ((nlogn)^1/2 + (t(n))^1/2)-tape bounded off-line Turing machine. These results improve or extend results by Chandra-Stockmeyer, Lipton-Tarjan and Paterson. A preliminary version of this paper was presented at the 19th IEEE-FOCS