Search

Abstract geometrical computation can solve NP-complete problems efficiently: any boolean constraint satisfaction problem, instance of SAT, can be solved in bounded space and time with simple geometrical constructions involving only drawing parallel lines on a Euclidean space-time plane. Complexity as the maximal length of a sequence of consecutive segments is quadratic. The geometrical algorithm achieves massive parallelism: an exponential number of cases are explored simultaneously. The construction relies on a fractal pattern and requires the same amount of space and time independently of the SAT formula. [ABSTRACT FROM AUTHOR]

Extended Signal machines are proven able to compute any computable function in the understanding of recursive/computable analysis (CA), here type-2 Turing machines (T2-TM) with signed binary encoding. This relies on an intermediate representation of any real number as an integer (in signed binary) plus an exact value in ( − 1,1) which allows to have only finitely many signals present outside of the computation. Extracting a (signed) bit, improving the precision by one bit and iterating the T2-TM only involve standard signal machines. For exact CA-computations, T2-TM have to deal with an infinite entry and to run through infinitely many iterations to produce an infinite output. This infinite duration can be provided by constructions emulating the black hole model of computation on an extended signal machine. Extracting/encoding an infinite sequence of bits is achieved as the limit of the approximation process with a careful handling of accumulations and singularities. [ABSTRACT FROM AUTHOR]

Abstract geometrical computation naturally arises as a continuous counterpart of cellular automata. It relies on signals (dimensionless points) traveling at constant speed in a continuous space in continuous time. When signals collide, they are replaced by new signals according to some collision rules. This simple dynamics relies on real numbers with exact precision and is already known to be able to carry out any (discrete) Turing-computation. The Blum, Shub and Small (BSS) model is famous for computing over ℝ (considered here as a ℝ unlimited register machine) by performing algebraic computations. We prove that signal machines (set of signals and corresponding rules) and the infinite-dimension linear (multiplications are only by constants) BSS machines can simulate one another. [ABSTRACT FROM AUTHOR]

An existence or non-existence of five-state firing squad synchronization protocol has been a long-standing, famous open problem for a long time. In this paper, we answer partially to this problem by proposing a smallest five-state firing squad synchronization algorithm that can synchronize any one-dimensional cellular array of length n = 2k in 3n − 3 steps for any positive integer k. The number five is the smallest one known at present in the class of synchronization protocols proposed so far. [ABSTRACT FROM AUTHOR]

A variant of Circuit Value Problem over the basis of Peirce's arrow (NOR) is introduced, in which one of the inputs of every k-th gate must be the (k − 1)-th gate. The problem, which remains P-complete, is encoded as a simple formal language over a two-letter alphabet. It is shown that this language can be naturally and succinctly represented by language equations from several classes. Using this representation, a small conjunctive grammar and an even smaller LL(1) Boolean grammar for this language are constructed. [ABSTRACT FROM AUTHOR]

Inspired by genetic programming (GP), we study iterative algorithms for non-computable tasks and compare them to naive models. This framework justifies many practical standard tricks from GP and also provides complexity lower-bounds which justify the computational cost of GP thanks to the use of Kolmogorov's complexity in bounded time. [ABSTRACT FROM AUTHOR]

Relations between such concepts as reducibility, universality, hardness, completeness, and deductibility are studied. The aim is to build a flexible and comprehensive theoretical foundations for different techniques and ideas used in computer science. It is demonstrated that: concepts of universality of algorithms and classes of algorithms are based on the construction of reduction of algorithms; concepts of hardness and completeness of problems are based on the construction of reduction of problems; all considered concepts of reduction, as well as deduction in logic are kinds of reduction of abstract properties. The Church-Turing Thesis, which states universality of the class of all Turing machines, is considered in a mathematical setting as a theorem proved under definite conditions. [ABSTRACT FROM AUTHOR]

We present a new family of solutions to the firing squad synchronization problem. All these solutions are built with a few finite number of signals, which lead to simple implementations with 7 or 8 internal states. Using one of these schemes we are able to built a 7-states $4n+\mathcal{O}(\log n)$-steps solution to the firing squad synchronization problem. These solutions not only solves the unrestricted problem (initiator at one of the two ends), but also the problem with initiators at both ends and the problem on a ring. [ABSTRACT FROM AUTHOR]

We present two small universal Turing machines that have 3 states and 7 symbols, and 4 states and 5 symbols respectively. These machines are semi-weak which means that on one side of the input they have an infinitely repeated word and on the other side there is the usual infinitely repeated blank symbol. This work can be regarded as a continuation of early work by Watanabe on semi-weak machines. One of our machines has only 17 transition rules making it the smallest known semi-weakly universal Turing machine. Interestingly, our two machines are symmetric with Watanabe's 7-state and 3-symbol, and 5-state and 4-symbol machines, even though we use a different simulation technique. [ABSTRACT FROM AUTHOR]

In place of the traditional definition of a cellular automaton CA = (S, Q, N, f), a new definition (S, Q, fn, ν) is given by introducing an injection called the neighborhood functionν: {0, 1,...,n − 1}→S, which provides a connection between the variables of local function fn of arity n and neighbors of CA: image(ν) is a neighborhood of size n. The new definition allows new analysis of cellular automata. We first show that from a single local function countably many CA are induced by changing ν and then prove that equivalence problem of such CA is decidable. Then we observe what happens if we change the neighborhood. As a typical research topics, we show that reversibility of 2 states 3 neighbors CA is preserved from changing the neighborhood, but that of 3 states CA is not. [ABSTRACT FROM AUTHOR]

A nondeterministic restarting automaton M is said to be (strongly) correctness preserving, if, for each cycle $u\vdash_M^c v$, the word v belongs to the complete language LC(M) accepted by M, if the word u does. Here, in order to differentiate between nondeterministic restarting automata that are correctness preserving and nondeterministic restarting automata in general we introduce two gradual relaxations of the correctness preserving property. These relaxations lead to an infinite two-dimensional hierarchy of classes of languages with membership problems that are decidable in polynomial time. [ABSTRACT FROM AUTHOR]

We present small polynomial time universal Turing machines with state-symbol pairs of (5,5), (6,4), (9,3) and (18,2). These machines simulate our new variant of tag system, the bi-tag system and are the smallest known universal Turing machines with 5, 4, 3 and 2-symbols respectively. Our 5-symbol machine uses the same number of instructions (22) as the smallest known universal Turing machine by Rogozhin. [ABSTRACT FROM AUTHOR]

It was shown in (Verlan, 2005) that complexity measures for insertion-deletion systems need a revision and new complexity measures taking into account the sizes of both left and right context were proposed. In this article we investigate insertion-deletion systems having a context only on one side of insertion or deletion rules. We show that a minimal deletion (of one symbol) in one-symbol one-sided context is sufficient for the computational completeness if a cooperation of 4 symbols is used for insertion rules and not sufficient if an insertion of one symbol in one-symbol left and right context is used. We also prove the computational completeness for the case of the minimal context-free deletion (of two symbols) and insertion of two symbols in one-symbol one-sided context. [ABSTRACT FROM AUTHOR]

In this paper we simplify accepting networks of splicing processors considered in [8] by moving the filters from the nodes to the edges. Each edge is viewed as a two-way channel such that input and output filters coincide. Thus, the possibility of controlling the computation in such networks seems to be diminished. In spite of this and of the fact that splicing alone is not a very powerful operation these networks are still computationally complete. As a consequence, we propose characterizations of two complexity classes, namely NP and PSPACE, in terms of accepting networks of restricted splicing processors with filtered connections. [ABSTRACT FROM AUTHOR]

A not well-known result [9, Theorem 4.4] in formal language theory is that the Higman-Haines sets for any language are regular, but it is easily seen that these sets cannot be effectively computed in general. Here the Higman-Haines sets are the languages of all scattered subwords of a given language and the sets of all words that contain some word of a given language as a scattered subword. Recently, the exact level of unsolvability of Higman-Haines sets was studied in [10]. We focus on language families whose Higman-Haines sets are effectively constructible. In particular, we study the size of Higman-Haines sets for the lower classes of the Chomsky hierarchy, namely for the families of regular, linear context-free, and context-free languages, and prove upper and lower bounds on the size of these sets. [ABSTRACT FROM AUTHOR]

The Skolem machine is a Turing-complete machine model where the instructions are first-order formulas of a specific form. We introduce Skolem machines and prove their logical completeness. Skolem machines compute queries for the Geolog language, a rich fragment of first-order logic. The concept of complete Geolog trees is defined, and this tree concept is used to show logical completeness for Skolem machines: If the query for a Geolog theory is a logical consequence of the axioms then the corresponding Skolem machine halts succesfully in a configuration that supports the query. [ABSTRACT FROM AUTHOR]

In this paper we will give an outline of the proof of the solvability of the halting and reachability problem for 2-symbolic tag systems with a deletion number v = 2. This result will be situated in a more general context of research on limits of solvability in tag systems. [ABSTRACT FROM AUTHOR]

We discuss the power of networks of evolutionary processors where only two types of nodes are allowed. We prove that (up to an intersection with a monoid) every recursively enumerable language can be generated by a network with one deletion and two insertion nodes. Networks with an arbitrary number of deletion and substitution nodes only produce finite languages, and for each finite language one deletion node or one substitution node is sufficient. Networks with an arbitrary number of insertion and substitution nodes only generate context-sensitive languages, and (up to an intersection with a monoid) every context-sensitive language can be generated by a network with one substitution node and one insertion node. [ABSTRACT FROM AUTHOR]

Confluent rewrite systems for giant trivalent networks have been investigated by S. Wolfram as possible models of space and spacetime, in the ambitious search for the most fundamental, computational laws of physics. We restrict here to planar trivalent nets, which are shown to support Turing-complete computations, and take an even more radical, approach: while operating on network duals, we use just one elementary rewrite rule and drive its application by a simple, fully deterministic algorithm, rather than by pattern-matching. We devise effective visual indicators for exploring the complexity of computations with elementary initial conditions, consisting of thousands of graphs, and expose a rich variety of behaviors, from regular to random-like. Among their features we study, in particular, the dimensionality of the emergent space. [ABSTRACT FROM AUTHOR]

Holzer and Holzer [HH04] proved that the TantrixTM rotation puzzle problem is NP-complete. They also showed that for infinite rotation puzzles, this problem becomes undecidable. We study the counting version and the unique version of this problem. We prove that the satisfiability problem parsimoniously reduces to the TantrixTM rotation puzzle problem. In particular, this reduction preserves the uniqueness of the solution, which implies that the unique TantrixTM rotation puzzle problem is as hard as the unique satisfiability problem, and so is DP-complete under polynomial-time randomized reductions, where DP is the second level of the boolean hierarchy over NP. [ABSTRACT FROM AUTHOR]

It is known that the satisfiability problem (SAT) can be solved with a semi-uniform family of deterministic polarizationless P systems with active membranes with non-elementary membrane division. We present a double improvement of this result by showing that the satisfiability of a quantified Boolean formula (QSAT) can be solved by a uniform family of P systems of the same kind. [ABSTRACT FROM AUTHOR]

We consider a new variant of the halting condition in P systems, i.e., a computation in a P system is already called halting if not for all membranes a rule is applicable anymore at the same time, whereas usually a computation is called halting if no rule is applicable anymore in the whole system. This new variant of partial halting is especially investigated for several variants of P systems using membrane rules with permitting contexts and working in different derivation modes. [ABSTRACT FROM AUTHOR]

Array-rewriting P systems were introduced in [2] linking the two areas of membrane computing and picture grammars. Subsequently a variety of P systems with array objects and different kinds of rewriting has been introduced. Here we discuss a few prominent systems among these, point out their features and indicate possible problems for future study. [ABSTRACT FROM AUTHOR]

A reversible Turing machines is a computing model with a "backward deterministic" property, which is closely related to physical reversibility. In this paper, we study the problem of finding a small universal reversible Turing machine (URTM). As a result, we obtained a 17-state 5-symbol URTM in the quintuple form that can simulate any cyclic tag system. [ABSTRACT FROM AUTHOR]

This is a survey of some of my joint work with Sylvain Périfel. It is focused on transfer theorems that connect boolean complexity to algebraic complexity in the Valiant and Blum-Shub-Smale models. [ABSTRACT FROM AUTHOR]

We give a new proof for the undecidability of the tiling problem. Then we show how the proof can be modified to demonstrate the undecidability of the tiling problem on the hyperbolic plane, thus answering an open problem posed by R.M.Robinson 1971 [6]. [ABSTRACT FROM AUTHOR]

Infinite time Turing machines extend the operation of ordinary Turing machines into transfinite ordinal time, thereby providing a natural model of infinitary computability, with robust notions of computability and decidability on the reals, while remaining close to classical concepts of computability. Here, I survey the theory of infinite time Turing machines and recent developments. These include the rise of infinite time complexity theory, the introduction of infinite time computable model theory, the study of the infinite time analogue of Borel equivalence relation theory, and the introduction of new ordinal computational models. The study of infinite time Turing machines increasingly relies on the interaction of methods from set theory, descriptive set theory and computability theory. [ABSTRACT FROM AUTHOR]

We use our method of approximation to relate various classes of computable functions over the reals. In particular, we compare Computable Analysis to the two analog models, the General Purpose Analog Computer and Real Recursive Functions. There are a number of existing results in the literature showing that the different models correspond exactly. We show how these exact correspondences can be broken down into a two step process of approximation and completion. We show that the method of approximation has further application in relating classes of functions, exploiting the transitive nature of the approximation relation. This work builds on our earlier work with our method of approximation, giving more evidence of the breadth of its applicability. [ABSTRACT FROM AUTHOR]

We review some results about the computational power of several computational models. Considered models have in common to be related to continuous dynamical systems. [ABSTRACT FROM AUTHOR]

Reaction-diffusion computers employ propagation of chemical and excitation waves to transmit information; they use collisions between traveling wave-fronts to perform computation. We increase applicability domain of the reaction-diffusion computers by encapsulating them in a membrane, in a form of vegetative state, plasmodium, of true slime mold. In such form reaction-diffusion computers can also realize Kolmogorov-Uspensky machine. [ABSTRACT FROM AUTHOR]

In Abstract geometrical computation for black hole computation (MCU '04, LNCS 3354), the author provides a setting based on rational numbers, abstract geometrical computation, with super-Turing capability. In the present paper, we prove the Turing computing capability of reversible conservative abstract geometrical computation. Reversibility allows backtracking as well as saving energy; it corresponds here to the local reversibility of collisions. Conservativeness corresponds to the preservation of another energy measure ensuring that the number of signals remains bounded. We first consider 2-counter automata enhanced with a stack to keep track of the computation. Then we built a simulation by reversible conservative rational signal machines. Keywords: Abstract geometrical computation, Conservativeness, Rational numbers, Reversibility, Turing-computability, 2-counter automata. [ABSTRACT FROM AUTHOR]

In Abstract geometrical computation for black hole computation (MCU '04, LNCS 3354), the author provides a setting based on rational numbers, abstract geometrical computation, with super-Turing capability: any recursively enumerable set can be decided in finite time. To achieve this, a Zeno-like construction is used to provide an accumulation similar in effect to the black holes of the black hole model. We prove here that forecasting an accumulation is Σ20-complete (in the arithmetical hierarchy) even if only energy conserving signal machines are addressed (as in the cited paper). The Σ20-hardness is achieved by reducing the problem of deciding whether a recursive function (represented by a 2-counter automaton) is strictly partial. The Σ20-membership is proved with a logical characterization. Keywords: Abstract geometrical computation, Accumulation forecasting, Arithmetical hierarchy, Black hole model, Energy conservation, Super-Turing computation, Turing universality, Zeno phenomena. [ABSTRACT FROM AUTHOR]

The Black hole model of computation provides super-Turing computing power since it offers the possibility to decide in finite (observer's) time any recursively enumerable ($\mathcal{R.E.}$) problem. In this paper, we provide a geometric model of computation, conservative abstract geometrical computation, that, although being based on rational numbers, has the same property: it can simulate any Turing machine and can decide any $\mathcal{R.E.}$ problem through the creation of an accumulation. Finitely many signals can leave any accumulation, and it can be known whether anything leaves. This corresponds to a black hole effect. [ABSTRACT FROM AUTHOR]

In the Cellular Automata (CA) literature, discrete lines inside (discrete) space-time diagrams are often idealized as Euclidean lines in order to analyze a dynamics or to design CA for special purposes. In this article, we present a parallel analog model of computation corresponding to this idealization: dimensionless signals are moving on a continuous space in continuous time generating Euclidean lines on (continuous) space-time diagrams. Like CA, this model is parallel, synchronous, uniform in space and time, and uses local updating. The main difference is that space and time are continuous and not discrete (ie instead of ). In this article, the model is restricted to in order to remain inside Turing-computation theory. We prove that our model can carry out any Turing-computation through two-counter automata simulation and provide some undecidability results. Keywords: Abstract geometrical computation, Analog model of computation, Cellular automata, Geometry, Turing universality. [ABSTRACT FROM AUTHOR]