Catálogo de publicaciones - libros

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.

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

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.

We use our method of approximation to relate various classes of computable functions over the reals. In particular, we compare to the two analog models, the and . 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 . 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.

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.

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].

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.

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.

Array-rewriting systems were introduced in [2] linking the two areas of membrane computing and picture grammars. Subsequently a variety of 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.

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.