Search

We discuss the formalization, in the Matita Theorem Prover, of basic results on multi-tapes Turing machines, up to the existence of a (certified) Universal Machine, and propose it as a natural benchmark for comparing different interactive provers and assessing the state of the art in the mechanization of formal reasoning. The work is meant to be a preliminary step towards the creation of a formal repository in Complexity Theory, and is a small piece in our long-term Reverse Complexity program, aiming to a comfortable, machine independent axiomatization of the field.

Recent cyberattacks have demonstrated that current approaches to the malware problem (e.g., detection) are inadequate. This is not surprising as virus detection is Turing undecidable. 1 Further, some recent malware implementations use NP problems to encrypt and hide the malware. 2 Two goals guide an alternative approach: (a) Program execution should hide computational steps in order to hinder “reverse engineering” efforts by malware hackers; (b) New computational models should be explored that make it more difficult to hijack the purpose of program execution. The methods explained here pertain to (a) implemented with a new computational model, called the active element machine (AEM). 3 An AEM is composed of computational primitives called active elements that simultaneously transmit and receive pulses to and from other active elements. Each pulse has an amplitude and a width, representing how long the pulse amplitude lasts as input to the active element receiving the pulse. If active element Ei simultaneously receives pulses with amplitudes summing to a value greater than Ei’s threshold and Ei’s refractory period has expired, then Ei fires. When Ei fires, it sends pulses to other active elements. If Ei fires at time t, a pulse reaches element Ek at time t+ τik where τik is the transmission time from Ei to Ek. The AEM language uses five commands – Element, Connection, Fire, Program and Meta – to write AEM programs, where time is explicitly specified and multiple commands may simultaneously execute. An Element command creates, at the time specified in the command, an active element with a threshold value, a refractory period and a most recent firing time. A Connection command sets, at the time specified in the command, a pulse amplitude, a pulse width and a transmission time from element Ei to element Ek. The Fire command fires an input element at a particular time. The Program command defines the execution of multiple commands with a single command. Element and Connection commands establish the AEM architecture and firing activity. The Meta command can change the AEM architecture during AEM program execution. This model uses quantum random input to generate random firing patterns that deterministically execute a universal Turing machine (UTM) program η. Random firing interpretations are constructed with dynamic level sets on boolean functions that compute η. The quantum randomness is an essential component for building the random firing patterns that are Turing incomputable. 4 It is assumed that the following are all kept perfectly secret: the state and tape of the UTM, represented by the active elements and connections; the quantum random bits determining how η is computed for each computational step; and the dynamic connections in the AEM. Formally, let f1j , f2j , . . . fmj represent the random firing pattern computing η during the jth computational step and assume an adversary can eavesdrop on f1j , f2j , . . . fmj . Let q denote the current state of the UTM, ak a UTM alphabet symbol and qk a UTM state. Perfect secrecy means that probabilities P (q = qk|f1j = b1 . . . fmj = bm) = P (q = qk) and P (Tk = ak|f1j = b1 . . . fmj = bm) = P (Tk = ak) for each bi ∈ {0, 1} and each Tk which is the contents of the kth tape square. If these secrecy conditions hold, then there doesn’t exist a “reverse engineer” Turing machine that can map the random firing patterns back to an unbounded sequence of UTM instructions. For an unbounded number of computational steps, define function g : N→ {0, 1} where g((j − 1)m+ r) = f(r+1)j and 0 ≤ r < m. Then g is incomputable. Proposed methods of hypercomputation currently have no physical realization. 5 The methods described here can be physically realized using an off-the-shelf quantum random generator device with a USB plug connected to a laptop computer executing a finite AEM program.

International audience; Deterministic one-way Turing machines with sublinear space bounds are systematically studied. We distinguish among the notions of strong, weak, and restricted space bounds. The latter is motivated by the study of P automata. The space available on the work tape depends on the number of input symbols read so far, instead of the entire input. The class of functions space constructible by such machines is investigated, and it is shown that every function f that is space constructible by a deterministic two-way Turing machine, is space constructible by a strongly f space-bounded deterministic one-way Turing machine as well. We prove that the restricted mode coincides with the strong mode for space constructible functions. The known infinite, dense, and strict hierarchy of strong space complexity classes is derived also for the weak mode by Kolmogorov complexity arguments. Finally, closure properties under AFL operations, Boolean operations and reversal are shown.

We prove a number of results in effective randomness, using methods in which Π10 classes play an essential role. The results proved include the fact that every PA Turing degree is the join of two random Turing degrees, and the existence of a minimal pair of LR degrees below the LR degree of the halting problem.

In this paper, we improve some results regarding the size complexity of accepting hybrid networks of evolutionary processors (AHNEPs). We show that there are universal AHNEPs of size 6, by devising a method for simulating 2-tag systems. This result improves the best upper bound for the size of universal AHNEPs which was 7. We also propose a computationally and descriptionally efficient simulation of nondeterministic Turing machines with AHNEPs. More precisely, we prove that AHNEPs with ten nodes can simulate any nondeterministic Turing machine of time complexity f (n) in time O(f (n)). This result significantly improves the best known upper bound for the number of nodes in a network simulating in linear time an arbitrary Turing machine, namely 24.

In this paper we formally define the notion of persistent Turing machines to model interactive computations. We compare the power of persistent Turing machines with respect to computing functions and relations and accepting sets with their classical counterparts. It turns out that the model of persistent computations leads to new characterizations of known function and language classes as well as to classes that have no classical counterpart.

We say that A≤LRB if every B-random set is A-random with respect to Martin–Lof randomness. We study this relation and its interactions with Turing reducibility, π10 classes, hyperimmunity and other recursion theoretic notions.

There is a dependency between computability of algorithmic complexity and decidability of different algorithmic problems. It is known that computability of the algorithmic complexity C(x) is equivalent to decidability of the halting problem for Turing machines. Here we extend this result to the realm of superrecursive algorithms, considering algorithmic complexity for inductive Turing machines. We study two types of algorithmic complexity: recursive (classical) and inductive algorithmic complexities. Relations between these types of algorithmic complexity and decidability of algorithmic problems for Turing machines and inductive Turing machines are considered. In particular, it is demonsrated that computability of algorithmic complexity is equivalent not only to decidability of the halting problem, but also to decidability by inductive Turing machines of the first order of many other problems for Turing machines, such as: if a Turing machine computes a recursive (total) function; if a Turing machine gives no result only for n inputs; if a Turing machine gives results only for n inputs.

We propose a construction of an accepting hybrid network of evolutionary processors (AHNEP) which behaves as a universal device in the class of all these devices. We first construct a Turing machine which can simulate any AHNEP and then an AHNEP which simulates the Turing machine. We think that this approach can be applied to other bio-inspired computing models which are computationally complete.

We prove that the existential theory of the Turing degrees, in the language with Turing reduction, 0, and unary relations for the classes in the generalized high/low hierarchy, is decidable. We also show that every finite poset labeled with elements of (where is the partition of induced by the generalized high/low hierarchy) can be embedded in preserving the labels. Note that no condition is imposed on the labels.

This paper investigates a relationship among the accepting powers of deterministic, nondeterministic, and alternating one-pebble two-dimensional Turing machines, and shows that (i) nondeterminism are more powerful than determinism for o(log n) space-bounded one-pebble two-dimensional Turing machines whose input tapes are restricted to square ones, and (ii) alternation are more powerful than nondeterminism for f(m)+g(n) (resp., f(m) × g(n)) space-bounded one-pebble two-dimensional Turing machines, where f : N → N is an arbitrary monotonic nondecreasing funcion space-constractible by a deterministic one-pebble two-dimensional Turing machine, and g : N → N is an arbitrary function such that g(n) = o(log n) (resp., g(n) = o(log n/loglog n)).

Let f and g be functions from N to N. We write f g to denote that there exists a constant c > 0 such that for all but finitely many n it holds that f (n) ≤ c(gcn) + cn. We say that f and g are equivalent if f g and g f . In [SBR] Sapir et al. conjecture that for all nondeterministic time functions T that are (n2) the square root of T is equivalent to the time function of a nondeterministic Turing machine. In this note we study this conjecture. We show that the deterministic version of this conjecture is false. For every rational number α, 0 < α < 1, there is a deterministic time function T = (n2) such that T α is not equivalent to any time function of a deterministic Turing machine.

The free-spectrum and g-spectrum functions of a variety V are defined as fV(n) = “the size of the free algebra on n generators in V” and gV(n) = “the number of non-isomorphic algebras in V generated by n or fewer elements”, for any positive integer n. Thus V is locally finite iff for each positive integer n, fV(n) is a positive integer (and consequently gV(n) is a positive integer). If V is locally finite, then we have

We prove that the set of properties describable by a uniform sequence of first-order sentences using at most k + 1 distinct variables is exactly equal to the set of properties checkable by a Turing machine in DSPACE[nk] (where n is the size of the universe). This set is also equal to the set of properties describable using an iterative definition for a finite set of relations of arity k. This is a refinement of the theorem PSPACE = VAR[O[1]] [8]. We suggest some directions for exploiting this result to derive trade-offs between the number of variables and the quantifier depth in descriptive complexity.

We exhibit a construction which produces for every Turing machine T with two halting states μ0 and μ−1, an algebra B(T) (finite and of finite type) with the property that the variety generated by B(T) is residually large if T halts in state μ−1, while if T halts in state μ0 then this variety is residually bounded by a finite cardinal.

We characterise explicitly the decidable predicates on integers of Infinite Time Turing machines, in terms of admissibility theory and the constructible hierarchy. We do this by pinning down ζ, the least ordinal not the length of any eventual output of an Infinite Time Turing machine (halting or otherwise); using this the Infinite Time Turing Degrees are considered, and it is shown how the jump operator coincides with the production of mastercodes for the constructible hierarchy; further that the natural ordinals associated with the jump operator satisfy a Spector criterion, and correspond to the Lζ-stables. It also implies that the machines devised are “Σ2 Complete” amongst all such other possible machines. It is shown that least upper bounds of an “eventual jump” hierarchy exist on an initial segment.

A Stochastic Turing machine (STM) is a Turing machine that can perform nondeterministic and probabilistic moves and alternate between both types. Such devices are also called games against nature, Arthur-Merlin-games, or interactive proof systems with public coins. We investigate stochastic machines with space resources between constant and logarithmic size, and, in addition, constant or sublinear bounds on the number of alternations between nondeterministic and probabilistic moves. Lower space bounds are shown for a specific family of languages by exploiting combinatorial properties. These results imply an infinite hierarchy with respect to the number of alternations of STMs, and nonclosure properties of certain classes.

We develop probabilistic algorithms that solve problems of geometric elimination theory using small memory resources. These algorithms are obtained by means of the adaptation of a general transformation due to A. Borodin which converts uniform boolean circuit depth into sequential (Turing machine) space. The boolean circuits themselves are developed using techniques based on the computation of a primitive element of a suitable zero-dimensional algebra and diophantine considerations.

This paper introduces two-dimensional probabilistic Turing machines (2-ptm's), and investigates several properties of them. We first investigate a relationship between two-dimensional alternating finite automata (2-afa's) and 2-ptm's with error probability less than 1 2 and with sublogarithmic space, and show that there is a set of square tapes accepted by 2-afa, but not recognized by any o(log-n) space-bounded 2-ptm with error probability less than 1 2 . This partially solves an open problem in Okazaki et al. (Inform. Sci., to appear). We next investigate a space hierarchy of 2-ptm's with error probability less than 1 2 and with sublogarithmic space, and show that if L(n) is space-constructible by a two-dimensional Turing machine, there is a set of square tapes accepted by a strongly L(n) space-bounded two-dimensional deterministic Turing machine, but not recognized by any L(n) space-bounded 2-ptm with error probability less than 1 2 .

In this paper we compare recursively enumerable subsets of Rq in two computing models over real numbers: the Blum-Shub-Smale machine and the oracle Turing machine. We prove that any Turing RE open subset of Rq is a BSS RE set, while a Turing RE closed set may not be a BSS RE set. As an application we show that the Julia set of any computable hyperbolic polynomial is decidable in the Turing computing model.

Inoue et al. [A. Inoue, A. Ito, K. Inoue, T. Okazaki, Some properties of one-pebble Turing machines with sublogarithmic space, Theoret. Comput. Sci. 341 (2005) 138-149] conjectured that the language {ww | w ∈ {a, b}+} is not accepted by any alternating one-pebble Turing machine with sublogarithmic space. In this paper we disprove the conjecture by showing that there exists an alternating one-pebble Turing machine accepting the language in log log n space.

Currently, a complexity-class problem is proving the existence of one-way permutations: one-to-one and onto maps that are computationally ‘easy’, while their inverses are computationally ‘hard’. In what follows, we make use of Bennett’s algorithm of the reversible Turing machine (quantum information heat engine) to perform a cascade of two controlled-NOT gates to physically create a permutation operation. We show that by running this input-saving (Turing) machine backwards the critical inequality of Landauer’s thermodynamic limit is reversed, which provokes the symmetry-breaking of the quantum circuit based on two successive controlled-NOT quantum gates. This finding reveals that a permutation of controlled-NOT gates becomes one-way, provided that adiabatically immersed in a heat bath, which determines the condition of existence of a thermodynamically non-invertible bijection in polynomial-time, that would otherwise be mathematically invertible. This one-way bijection can also be particularly important because it shows nonlinearities in quantum mechanics, which are detectable by watching that the mathematical reversibility of controlled-NOT gates does not work physically.

In this paper, the problem of applying changes to software at runtime is con- sidered. The computability theory is used in order to develop a more general and programming-language-independent model of computation with support for runtime changes. Various types of runtime changes were defined in terms of computable functions and Turing machines. The properties of such functions and machines were used to prove that arbitrary runtime changes on Turing machines are impossible in general cases. A method of Turing machine decom- position into subtasks was presented and runtime changes were defined through transformations of the subtask graph. Requirements for the possible changes were considered with regard to the possibility of subtask execution during such changes. Finally, a runtime change model of computation was defined by exten- sion of the Universal Turing Machine.

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.

We introduce a class of safe Turing machines which execute structured while, if-then- else programs and operate on stacks and on a read-only input tape. A hierarchy is obtained by taking as Si the class of all functions computed by programs of loop-depth i. The main result is that S1 equals Lintime and S2 equals Polytime while, for i≥3, we have that Si equals the i-th Grzegorczyk class. By adding to the language a non-deterministic construct choose we take S2 into a class equivalent to NP. This gives a syntactical characterization in a pure-machine model of the mentioned classes.

It is shown that on a one-tape Turing machine the Element Distinctness Problem for short numbers (n numbers of log n bits each) is of time complexity Θ(n2log n).

We introduce a new so-called distance complexity measure for Turing machine computations which is sensitive to long-distance transfers of information on the worktape. An important special case of this measure can be interpreted as a kind of buffering complexity which counts the number of necessary block uploads into a virtual buffer on top of the worktape. Thus, the distance measure can be used for investigating the buffering aspects of Turing computations. In this paper, we start this study by proving a tight separation and hierarchy result. In particular, we show that a very small increase in the distance complexity bound (roughly from c(n) to c(n + 1) + constant) brings provably more computational power to both deterministic and nondeterministic Turing machines. For this purpose, we formulate a very general diagonalization method for Blum-like complexity measures. We also obtain a hierarchy of the distance complexity classes.

Based on the definition of single-tape Fuzzy Non-deterministic Turing Machine (FNTM), this article discussed in details the process of FNTM accepting language and researched the computational complexity of fuzzy Turing Machine (TM) accepting ?-cut language by using the Deterministic Turing Machine (DTM) to simulate its process, thus drawing the conclusion that the judgment of FNTM accepting ?-cut language is a matter of the NP-completeness, and that it is not essentially helpful to adjust the membership degree in facing the time complexity problem when simulating the process of FNTM accepting the language.

Various methods exists in the litearture for denoting the configuration of a Turing Machine. A key difference is whether the head position is indicated by some integer (mathematical representation) or is specified by writing the machine state next to the scanned tape symbol (intrinsic representation). From a mathematical perspective this will make no difference. However, since Turing Machines are primarily used for proving undecidability and/or hardness results these representations do matter. Based on a number of applications we show that the intrinsic representation should be preferred.

It is shown that the Element Distinctness Problem ( n numbers of k log n bits each, k ⩾ 2) on a one-tape Turing machine takes time proportional to almost the square of the size of the input. The proof holds for both deterministic and nondeterministic Turing machines. This proof improves the best known lower bound of Ω( n 2 log n ) for deterministic Turing machines and of Ω(nlog 2 n) (B. Kalyanasundaram and G. Schnitger (1992)) for nondeterministic Turing machines to Ω(n 2 log n) . The lower bound is generalized to the n -Element Distinctness problem; on inputs of size N = nm, with 1 ⩽ n log N , it is shown to take time Ω(max{ Nn , Nm }). The proof makes use of Kolmogorov Complexity.

We enhance the notion of a computation of the classical theory of computing with the notion of interaction. In this way, we enhance a Turing machine as a model of computation to a Reactive Turing Machine that is an abstract model of a computer as it is used nowadays, always interacting with the user and the world.

In this paper we consider three variants of accepting networks of evolutionary processors. It is known that two of them are equivalent to Turing machines. We propose here a direct simulation of one device by the other. Each computational step in one model is simulated in a constant number of computational steps in the other one while a translation via Turing machines squares the time complexity. We also discuss the possibility of constructing simulations that preserve not only complexity, but also the shape of the simulated network. © 2011 Springer Science+Business Media B.V., This work was supported by the Academy of Finland, projects 132727, 122426, and 108421. F. Manea acknowledges the support from the Alexander von Humboldt Foundation. J Sempere acknowledges the support from the Spanish Ministerio de Educacion y Ciencia project TIN2007-60769.

This paper deals with the accepting powers of five-way three-dimensional alternating machines and six-way three-dimensional alternating machines whose input tapes are restricted to cubic ones. We first show that for space smaller than log m , five-way three-dimensional alternating Turing machines are less powerful than six-way three-dimensional alternating Turing machines. We then show that the set of all the three-dimensional connected tapes can be accepted by a six-way three-dimensional alternating finite automaton, but not accepted by any o (log m ) space-bounded five-way three-dimensional alternating Turing machine. Finally, we show that there exists a language accepted by a five-way three-dimensional alternating finite automaton, but not accepted by any o (log m ) space-bounded six-way three-dimensional nondeterministic Turing machine.

To examine the concept of random generation in bounded, as opposed to expected, polynomial time, a model of a probabilistic Turing machine (PTM) with the ability to make random choices with any (small) rational bias is necessary. This ability is equivalent to that of being able to simulate rolling any k-sided die (where [k] is polynomial in the length of the input). We would like to minimize the amount of hardware required for a machine with this capability. This leads to the problem of efficiently simulating a family of dice with a few different types of biased coins as possible. In the special case of simulating one n-sided die, we prove that only two types of biased coins are necessary, which can be reduced to one if we allow irrationally biased coins. This simulation is efficient, taking O(log n) coin flips. For the general case we get a tight time vs number of biases tradeoff; for example, with O(log n) different biases, we can simulate, for any i < n, an i-sided die in O(log n) coin flips.

We present almost matching upper and lower time bounds for the simulation of Turing machines with many queues, tapes, or stacks on Turing machines with few queues. In particular, the power of two queues in comparison with other storage types is clarified. We show that t ( n )-time-bounded multistorage Turing machines can be simulated in time O( t ( n ) 1 + 1/ k ) on k -queue machines. Every online simulation of k + 1 queues (or of two tapes) on k queues requires time Ω( t ( n ) 1 + 1/ k /polylog t ( n )). The lower bounds are based on Kolmogorov complexity.

A series of existing lower bound results for deterministic one-tape Turing machines is extended to another, stronger such model suitable for the computation of functions: one-tape off-line Turing machines with a write-only output tape. (“Off-line” means: having a two-way input tape.) The following optimal lower bound is shown: Computing the transpose of Boolean l × l -matrices takes Ω( l 5 2 )=Ω( n 5 4 ) steps on such Turing machines. ( n = l 2 is the length of the input.)

One of the common results of resource bounded Turing machines is the $\log \log n$ lower bound for the space usage of deterministic and nondeterministic Turing machines that accept nonregular languages. In this paper this result is extended to alternating Turing machines: It is proved that if $f(n) = o(\log \log n)$, then $f(n)$-space-bounded (off-line) alternating Turing machines can accept only regular sets. The problem has been open for a decade.

Turing-computable issue is important in research of Turing Machine and has significant value in both theory and practice. The paper analyzes Turing-computable issue of non-negative numbers by relational operations(includes greater than, less than and equal) and arithmetic operations(includes add operation, subtract, multiply, divide and modulo). The regulation of computing 1-bit binary number and the carry set(or borrow set) are defined to compute multi-bit binary numbers. Algorithms are described through multi-tape Turing machine. For some operations, the discussion is extended to base-N number system(3≤N≤10). Turing regulation for add operation is used to implement the Turing counter for counting the length of the string on the input tape of the Turing machine.

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 Ω(n1 + (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(t2(logt)1/2) time ifd = 2, and inO(t2) time ifd ≥ 3. This result uses the weight-balanced trees of Nievergelt and Reingold.

The construction of an optical computer that can explore the computation tree of a non-deterministic Turing machine in the time it takes to explore one path of the computation has been described in Dolev and Nir 2003. In this paper, we elaborate on the design considerations of Dolev and Nir 2003. The construction of such an optical computer will allow solving NP problems in polynomial time. The limitation is space, where every beam location (hitting a prism) represents a different Turing machine configuration. By the use of writable (holographic) memory, we are able to reduce the space only by a constant factor. Tradeoffs between the use of semantics for each location in space, and the use of digital storage is discussed. In the writable model, configurations can be represented in binary (or higher base digital) representation, rather than mapping each location in space to a single configuration. We show that, the benefit of such a digital representation in the scope of concurrent exhaustive search is limited.

The following problems about time-bounded program-size complexity are studied: (1) for a given string x, a size bound s, and a time bound t, whether there exists a Turing machine of size less than or equal to s that prints x in t moves; (2) for two given finite sets Y and Z of strings, a size bound s, and a time bound t, whether there exists a Turing machine of size less than or equal to s that operates in time t and accepts all $y \in Y$ and rejects all $z \in Z$. These problems are fundamental in complexity theory and feasible learning theory. The complexity of these problems is apparently between P and $NP$, but appears very difficult to classify precisely. These problems are attacked by the approach of relativization. It is shown that for certain variations of the problems, they could be either polynomial-time computable or not polynomial-time computable, depending on different oracles. Furthermore, there are oracles relative to which they are not complete for $NP$ under the polynomial-time Turing red...

A new method is given for obtaining a boolean expression whose satisfiability is equivalent to the existence of an accepting computation of some nondeterministic machine. Although starting from random access machines, this method gives an expression of the same O( T log T ) length as the best reduction from general Turing machines.

In this paper, a dynamic model of computation based on the Universal Turing Machine is proposed. This model is capable of applying runtime code modifications for 3-symbol deterministic Turing Machines at runtime and requires a decomposition of the simulated machine into parts called subtasks. The algorithm for performing runtime changes is considered, and the ability to apply runtime changes is studied through computer simulations. Theoretical properties of the proposed model, including computational power as well as time and space complexity, are studied and proven. Connections between the proposed model and Oracle Machines are discussed. Moreover, a possible method of implementation in real-life systems is proposed.

Reversal complexity on 1-tape and 2-tape Turing machine models discussed. We show that with respect to reversal complexity there is an intrinsic difference between 1-tape and 2-tape Turing machines. More precisely, we show that in the deterministic case, 2-tape Turing machines can simulate k-tape Turing machines without much increase in reversals while 1-tape Turing machines do not have such a property if P ≠ PSPACE; in the nondeterministic case, reversal complexity is “too” powerful to be a complexity measure on 2-tape Turing machines, but on 1-tape Turing machines it is a reasonable complexity measure which is linearly related to the space complexity.

The goal of this paper is to study the process of evolution of evolution. In other words, we study evolution that adapts evolutionary algorithms in parallel with their solutions. For this purpose, we define and investigate several extensions of evolutionary Turing machine model: self-constructing evolutionary Turing machines (SETM), self-constructing evolutionary Turing machines with a basic constructor (SBETM), self-constructing evolutionary Turing machines with a basic constructor and control information (CSBETM), and self-constructing evolutionary Turing machines with evolvable control information (CSETM). Such properties as expressiveness and complexity of different types of self-constructing evolutionary Turing machines are studied. It is demonstrated how self-constructive abilities allow one to essentially increase efficiency of evolutionary processes in general and evolutionary computations, in particular. We also investigate computation and construction universatility in the context of these new models.

Lots of efforts in the last decades have been done to prove or disprove whether the set of polynomially bounded problems is equal to the set of polynomially verifiable problems. This paper will present an overview of the current beliefs of quantum complexity theorists and discussion detail the impacts these beliefs may have on the future of the field. We introduce a new form of Turing machine based on the concepts of quantum mechanics and investigate the domain of this novel definition for computation. The main object is to show the domain of these computation machines and the new definition of algorithms using these automata. In section one we give a brief fundamental overview of classical complexity theory, Turing machine and all the fundamental concepts required for the next chapters. In section two we describe various classes of classical complexity automata. In next chapter we introduce quantum complexity featuring quantum Turing machines and discuss its relationship to classical complexity. Section four presents a relationship between quantum complexity classes based on the quantum Turing machines and quantum oracles, and their relationship with corresponding classical complexity classes. And section five presents a discussion on the practical phenomena in problem solving using quantum computers. Finally in section five we speculate briefly on the direction we believe the field to be headed, and what might reasonably be expected in the future

In Turing Machines, the input string can be of size n, where n is any natural number. The memory tape of the Turing Machine may store symbols which in general, may depend on this parameter n. Using hard-limiter neurons, earlier we introduced a framework for simulating a Turing machine [5]. In our earlier schemes [5], for accessing one symbol on memory tape having m symbols, we needed the number of operations that depend (at least logarithmically) on m. In this paper, we introduce a framework for constant time access of any symbol on memory tape.

We introduce a new model of parallel computation, namely the FIFO nets. First, we introduce some basic definitions. A restriction of this model has the power of the Turing machine. Monogeneous Fifo nets are then introduced. The coverability tree is a procedure to decide whether a monogeneous net is bounded or not. At last, regularity is decidable for monogeneous nets.

We work in $ \mathcal{D}[

It is shown that a set is low for weakly 1-generic iff it has neither dnr nor hyperimmune Turing degree. As this notion is more general than being recursively traceable, this answers negatively a recent question on the characterization of these sets. Furthermore, it is shown that every set which is low for weakly 1-generic is also low for Kurtz-random.