On relationships between complexity classes of Turing machines

Classes of time and space complexity of Turing machines are defined, and relationships between them are discussed. New relationships between the defined complexity classes are described.     

Solvability of the halting problem for certain classes of Turing machines

One method of proving that some Turing machine is not universal is to prove that the halting problem is solvable for it. Therefore, to obtain a lower bound on the complexity of a universal machine, it is convenient to have a criterion of solvability of the halting problem. In the present paper, we establish some of these criteria; they are formulated in terms of properties of machine graphs and computations.Translated from Matematicheskie Zametki, Vol. 13, No. 6, pp. 899–909, June, 1973.In conclusion, the author wishes to thank S. V. Yablonskii for discussing this work, and for a number of valuable comments, as well as O. B. Lupanov for suggestions.     

Lattice-valued fuzzy Turing machines: Computing power, universality and efficiency

In this paper we study fuzzy Turing machines with membership degrees in distributive lattices, which we called them lattice-valued fuzzy Turing machines. First we give several formulations of lattice-valued fuzzy Turing machines, including in particular deterministic and non-deterministic lattice-valued fuzzy Turing machines (l-DTMcs and l-NTMs). We then show that l-DTMcs and l-NTMs are not equivalent as the acceptors of fuzzy languages. This contrasts sharply with classical Turing machines. Second, we show that lattice-valued fuzzy Turing machines can recognize n-r.e. sets in the sense of Bedregal and Figueira, the super-computing power of fuzzy Turing machines is established in the lattice-setting. Third, we show that the truth-valued lattice being finite is a necessary and sufficient condition for the existence of a universal lattice-valued fuzzy Turing machine. For an infinite distributive lattice with a compact metric, we also show that a universal fuzzy Turing machine exists in an approximate sense. This means, for any prescribed accuracy, there is a universal machine that can simulate any lattice-valued fuzzy Turing machine on it with the given accuracy. Finally, we introduce the notions of lattice-valued fuzzy polynomial time-bounded computation (lP) and lattice-valued non-deterministic fuzzy polynomial time-bounded computation (lNP), and investigate their connections with P and NP. We claim that lattice-valued fuzzy Turing machines are more efficient than classical Turing machines.     

Computing Schrödinger propagators on Type-2 Turing machines

We study Turing computability of the solution operators of the initial-value problems for the linear Schrödinger equation u_t=iΔu+φ and the nonlinear Schrödinger equation of the form iu_t=-Δu+mu+|u|²u. We prove that the solution operators are computable if the initial data are Sobolev functions but noncomputable in the linear case if the initial data are L^p-functions and p≠2. The computations are performed on Type-2 Turing machines.     

Infinite Time Turing Machines With Only One Tape

Infinite time Turing machines with only one tape are in many respects fully as powerful as their multi‐tape cousins. In particular, the two models of machine give rise to the same class of decidable sets, the same degree structure and, at least for partial functions f : ℝ → ℕ, the same class of computable functions. Nevertheless, there are infinite time computable functions f : ℝ → ℝ that are not one‐tape computable, and so the two models of infinitary computation are not equivalent. Surprisingly, the class of one‐tape computable functions is not closed under composition; but closing it under composition yields the full class of all infinite time computable functions. Finally, every ordinal that is clockable by an infinite time Turing machine is clockable by a one‐tape machine, except certain isolated ordinals that end gaps in the clockable ordinals.     

Notes on the complexity of sorting in abstract machines

The complexity of sorting with pointer machines and successor-predecessor random access machines is studied. The size of the problem is defined as the length of the problem string. A linear time algorithm is achieved for sorting by pointer machines. For successor-predecessor random access machines linear time is sufficient in a special case.     

Turing oracle machines, online computing, and three displacements in computability theory

We begin with the history of the discovery of computability in the 1930’s, the roles of Gödel, Church, and Turing, and the formalisms of recursive functions and Turing automatic machines (a-machines). To whom did Gödel credit the definition of a computable function? We present Turing’s notion [1939, §4] of an oracle machine (o-machine) and Post’s development of it in [1944, §11], [1948], and finally Kleene-Post [1954] into its present form.A number of topics arose from Turing functionals including continuous functionals on Cantor space and online computations. Almost all the results in theoretical computability use relative reducibility and o-machines rather than a-machines and most computing processes in the real world are potentially online or interactive. Therefore, we argue that Turing o-machines, relative computability, and online computing are the most important concepts in the subject, more so than Turing a-machines and standard computable functions since they are special cases of the former and are presented first only for pedagogical clarity to beginning students. At the end in §10–§13 we consider three displacements in computability theory, and the historical reasons they occurred. Several brief conclusions are drawn in §14.     

Turing patterns induced by cross-diffusion in a predator-prey system in presence of habitat complexity

In this paper, we have investigated the phenomena of Turing pattern formation in a predator-prey model with habitat complexity in presence of cross diffusion. Using the linear stability analysis, the conditions for the existence of stationary pattern and the existence of Hopf bifurcation are obtained. It is shown analytically that the presence of cross diffusion in the system supports the formation of Turing pattern. Two parameter bifurcation analysis are done analytically and corresponding bifurcation diagrams are presented numerically. A series of simulation results are plotted for different biologically meaningful parameter values. Effects of variation of habitat complexity and the predator mortality rate and birth rate of prey on pattern formation are also reported. It is shown that cross-diffusion can lead to a wide variety of spatial and spatiotemporal pattern formation. It is found that the model exhibits spot and stripe pattern, and coexistence of both spot and strip patterns under the zero flux boundary condition. It is observed that cross-diffusion, habitat complexity, birth rate of prey and predator’s mortality rate play a significant role in the pattern formation of a distributed population system of predator-prey type.     

On the complexity of scheduling unrelated parallel machines with limited preemptions

We consider the problem of finding a minimum-length preemptive schedule for n jobs on m parallel machines. The problem is solvable in polynomial time, whether the machines are identical, uniform or unrelated. For identical or uniform machines, it is easy to obtain an optimal schedule in which the portion of a job that is assigned to a single machine is processed without interruption. We show that imposing this condition in the case of unrelated machines makes the problem NP-hard.     

Turing pattern outside of the Turing domain

There are two simple solutions to reaction-diffusion systems with limit-cycle reaction kinetics, producing oscillatory behaviour. The reaction parameter mu gives rise to a 'space-invariant' solution, and mu versus the ratio of the diffusion coefficients gives rise to a 'time-invariant' solution. We consider the case where both solution types may be possible. This leads to a refinement of the Turing model of pattern formation. We add convection to the system and investigate its effect. More complex solutions arise that appear to combine the two simple solutions. The convective system sheds light on the underlying behaviour of the diffusive system.     

含有批处理机的三机流水作业加工总长问题的计算复杂性

研究含有批处理机的三台机器流水作业加工总长问题的计算复杂性.不仅考虑了批处理机容量有限的情形,还考虑了批处理机容量无限的情形.证明了当第二台机器是批处理机、其余两台机器是单机时,该问题是NP困难的.至此,含有批处理机的三台机器流水作业加工总长问题在所有情形下的计算复杂性得到了解决.     

The complexity of a cyclic scheduling problem with identical machines and precedence constraints

We consider a set T of tasks with unit processing times. Each of them must be executed infinitely often. A uniform constraint is defined between two tasks and induces a set of precedence constraints on their successive executions. We limit our study to a subset of uniform constraints corresponding to two hypotheses often verified in practice: Each execution of T must end by a special task f, and uniform constraints between executions from different iterations start from f. We have a fixed number of identical machines. The problem is to find a periodic schedule of T which maximizes the throughput. We prove that this problem is NP-hard and show that it is polynomial for two machines. We also present another nontrivial polynomial subcase which is a restriction of uniform precedence constraints.     

Time complexity of single machine scheduling with stochastic precedence constraints

This paper deals with single machine scheduling problems with stochastic precedence relations (so calledGERT networks). Until now most investigations on such problems, dealt with algorithms running in polynomial time. On the other hand, for scheduling problems with deterministic precedence relations exist a lot of results about time complexity. Therefore, the object of this paper is to consider time complexity of scheduling problems with stochastic precedence constraints and to describe the boundary between theNP-hard problems and those which can be solved in polynomial time.     

Sampling based on timing: Time encoding machines on shift-invariant subspaces

Sampling information using timing is an approach that has received renewed attention in sampling theory. The question is how to map amplitude information into the timing domain. One such encoder, called time encoding machine, was introduced by Lazar and Tóth (2004 [23]) for the special case of band-limited functions. In this paper, we extend their result to a general framework including shift-invariant subspaces. We prove that time encoding machines may be considered as non-uniform sampling devices, where time locations are unknown a priori. Using this fact, we show that perfect representation and reconstruction of a signal with a time encoding machine is possible whenever this device satisfies some density property. We prove that this method is robust under timing quantization, and therefore can lead to the design of simple and energy efficient sampling devices.     

Turing degrees of nonabelian groups

For a countable structure , the (Turing) degree spectrum of is the set of all Turing degrees of its isomorphic copies. If the degree spectrum of has the least degree , then we say that is the (Turing) degree of the isomorphism type of . So far, degrees of the isomorphism types have been studied for abelian and metabelian groups. Here, we focus on highly nonabelian groups. We show that there are various centerless groups whose isomorphism types have arbitrary Turing degrees. We also show that there are various centerless groups whose isomorphism types do not have Turing degrees.

     

Turing incomparability in Scott sets

For every Scott set and every nonrecursive set in , there is a such that and are Turing incomparable.