Relations between diagonalization,proof systems,and complexity gaps

In this paper we study diagonal processes over time bounded computations of one-tape Turing machines by diagonalizing only over those machines for which there exist formal proofs that they operate in the given time bound. This replaces the traditional “clock” in resource bounded diagonalization by formal proofs about running times and establishes close relations between properties of proof systems and existence of sharp time bounds for one-tape Turing machine complexity classes. These diagonalization methods also show that the Gap Theorem for resource bounded computations can hold only for those complexity classes which differ from the corresponding provable complexity classes. Furthermore, we show that there exist recursive time bounds T(n) such that the class of languages for which we can formally prove the existence of Turing machines which accept them in time T(n) differs from the class of languages accepted by Turing machines for which we can prove formally that they run in time T(n). We also investigate the corresponding problems for tape bound computations and discuss the difference time and tapebounded computations.     

Uniform simulations of nondeterministic real time multitape turing machines

A new and uniform technique is developed for the simulation of nondeterministic multitape Turing machines by simpler machines. For many types of restricted nondeterministic Turing machines it can now be proved that both linear time is no more powerful than real time, and multitape machines are no more powerful than machines with two tapes, one of which is a simple and normalized comparison tape. This is an improvement over all previously known simulations in terms of weaker machines. As an application we obtain that, for all such machines, the class of languages accepted in real time by multitape machines is principal and has a simple trio generator. Moreover, multitape machines with different types of tapes are hierarchically related, contrasting with the case of one-tape machines, and some important families of languages are characterized in a new way.     

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.     

Observations on complete sets between linear time and polynomial time

There is a single set that is complete for a variety of nondeterministic time complexity classes with respect to related versions of m-reducibility. This observation immediately leads to transfer results for determinism versus nondeterminism solutions. Also, an upward transfer of collapses of certain oracle hierarchies, built analogously to the polynomial-time or the linear-time hierarchies, can be shown by means of uniformly constructed sets that are complete for related levels of all these hierarchies. A similar result holds for difference hierarchies over nondeterministic complexity classes. Finally, we give an oracle set relative to which the nondeterministic classes coincide with the deterministic ones, for several sets of time bounds, and we prove that the strictness of the tape-number hierarchy for deterministic linear-time Turing machines does not relativize.     

Computational complexity via programming languages: constant factors do matter

The purpose of this work is to promote a programming-language approach to studying computability and complexity, with an emphasis on time complexity. The essence of the approach is: a programming language, with semantics and complexity measure, can serve as a computational model that has several advantages over the currently popular models and in particular the Turing machine. An obvious advantage is a stronger relevance to the practice of programming. In this paper we demonstrate other advantages: certain proofs and constructions that are hard to do precisely and clearly with Turing machines become clearer and easier in our approach, and sometimes lead to finer results. In particular, we prove several time hierarchy theorems, for deterministic and non-deterministic time complexity which show that, in contrast with Turing machines, constant factors do matter in this framework. This feature, too, brings the theory closer to practical considerations. The above result suggests that this framework may be appropriate for studying low complexity classes, such as linear time. As an example we give a problem complete for non-deterministic\/ linear time under deterministic linear-time reductions. Finally, we consider some extensions and modifications of our programming language and their effect on time complexity results. Received: 26 October 1998 / 9 June 2000     

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.     

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.     

Infinite Time Turing Machines

Infinite time Turing machines extend the operation of ordinary Turing machines into transfinite ordinal time. By doing so, they provide a natural model of infinitary computability, a theoretical setting for the analysis of the power and limitations of supertask algorithms.     

From Symbol to ‘Symbol’, to Abstract Symbol: Response to Copeland and Shagrir on Turing-Machine Realism Versus Turing-Machine Purism

In their recent paper “Do Accelerating Turing Machines Compute the Uncomputable?” Copeland and Shagrir (Minds Mach 21:221–239, 2011) draw a distinction between a purist conception of Turing machines, according to which these machines are purely abstract, and Turing machine realism according to which Turing machines are spatio-temporal and causal “notional" machines. In the present response to that paper we concede the realistic aspects of Turing’s own presentation of his machines, pointed out by Copeland and Shagrir, but argue that Turing's treatment of symbols in the course of that presentation opens the door for later purist conceptions. Also, we argue that a purist conception of Turing machines (as well as other computational models) plays an important role not only in the analysis of the computational properties of Turing machines, but also in the philosophical debates over the nature of their realization.     

Alternation on cellular automata

In this paper we consider several notions of alternation in cellular automata: non-uniform, uniform and weak alternation. We study relations among these notions and with alternating Turing machines. It is proved that the languages accepted in polynomial time by alternating Turing machines are those accepted by alternating cellular automata in polynomial time for all the proposed alternating cellular automata. In particular, this is true for the weak model where the difference between existential and universal states is omitted for all the cells except the first one. It is proved that real time alternation in cellular automata is strictly more powerful than real time alternation in Turing machines, with only one read-write tape. Moreover, it is shown that in linear time uniform and weak models agree.     

基于量子逻辑的图灵机及其通用性

基于量子逻辑的自动机理论是量子计算模型的一个重要研究方向.该文研究了基于量子逻辑的图灵机(简称量子图灵机)及其一些变形,给出了包括非确定型量子图灵机l-VTM,确定型量子图灵机l-VDTM以及相应类型的多带量子图灵机,并引入量子图灵机基于深度优先与宽度优先识别语言的两种不同定义方式,证明了这两种定义方式在量子逻辑意义下是不等价的.进一步证明了l-VTM、l-VDTM与相应类型的多带量子图灵机之间的等价性.其次,给出了量子递归可枚举语言及量子递归语言的定义,并给出了二者的层次刻画,证明了l-VTM与l-VDTM不等价,但两者作为量子递归语言的识别器是等价的.最后,文中讨论了基于量子逻辑的通用图灵机的存在性问题,给出了一套合理编码系统,证明了基于量子逻辑的通用图灵机在其所取值的正交模格无限时不存在,而在其所取值的正交模格有限时是存在的.     

Supermachines and Superminds

If the computational theory of mind is right, then minds are realized by machines. There is an ordered complexity hierarchy of machines. Some finite machines realize finitely complex minds; some Turing machines realize potentially infinitely complex minds. There are many logically possible machines whose powers exceed the Church–Turing limit (e.g. accelerating Turing machines). Some of these supermachines realize superminds. Superminds perform cognitive supertasks. Their thoughts are formed in infinitary languages. They perceive and manipulate the infinite detail of fractal objects. They have infinitely complex bodies. Transfinite games anchor their social relations.     

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.     

Linear-time simulation of multihead turing machines

The main result of this paper is that, given a Turing machine M with k-heads on a d-dimensional tape, one can effectively construct a Turing machine M′ with k d-dimensional tapes but only one head per tape and one additional linear single-head tape which simulates M in linear-time.     

On the computational complexity of spiking neural P systems

It is shown here that there is no standard spiking neural P system that simulates Turing machines with less than exponential time and space overheads. The spiking neural P systems considered here have a constant number of neurons that is independent of the input length. Following this, we construct a universal spiking neural P system with exhaustive use of rules that simulates Turing machines in linear time and has only 10 neurons.     

Some observations concerning alternating turing machines using small space

We make some observations concerning alternating Turing machines operating in small space. For example, we show that alternating Turing machines using o(log n) space are more powerful than nondeterministic Turing machines using the same space-bound. In fact, we show that there is a language over a unary alphabet that can be accepted by an on-line alternating Turing machine in log n space, but not by any off-line nondeterministic Turing machine in o(log n) space. We also investigate the weak vs. strong space bounds and on-line vs. off-line machines at these low tape bounds.     

Accelerating Turing Machines

Minds and Machines - Accelerating Turing machines are Turing machines of a sort able to perform tasks that are commonly regarded as impossible for Turing machines. For example, they can determine...     

Zeno machines and hypercomputation

This paper reviews the Church–Turing Thesis (or rather, theses) with reference to their origin and application and considers some models of “hypercomputation”, concentrating on perhaps the most straight-forward option: Zeno machines (Turing machines with accelerating clock). The halting problem is briefly discussed in a general context and the suggestion that it is an inevitable companion of any reasonable computational model is emphasised. It is suggested that claims to have “broken the Turing barrier” could be toned down and that the important and well-founded rôle of Turing computability in the mathematical sciences stands unchallenged.     

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.     

Universality and programmability of quantum computers

Manin, Feynman, and Deutsch have viewed quantum computing as a kind of universal physical simulation procedure. Much of the writing about quantum logic circuits and quantum Turing machines has shown how these machines can simulate an arbitrary unitary transformation on a finite number of qubits. The problem of universality has been addressed most famously in a paper by Deutsch, and later by Bernstein and Vazirani as well as Kitaev and Solovay. The quantum logic circuit model, developed by Feynman and Deutsch, has been more prominent in the research literature than Deutsch’s quantum Turing machines. Quantum Turing machines form a class closely related to deterministic and probabilistic Turing machines and one might hope to find a universal machine in this class. A universal machine is the basis of a notion of programmability. The extent to which universality has in fact been established by the pioneers in the field is examined and this key notion in theoretical computer science is scrutinised in quantum computing by distinguishing various connotations and concomitant results and problems.