Catálogo de publicaciones - libros

Is randomness in quantum mechanics “algorithmically random”? Is there any relation between Heisenberg’s uncertainty relation and Gödel’s incompleteness? Can quantum randomness be used to trespass the Turing’s barrier? Can complexity shed more light on incompleteness? In this paper we use variants of “algorithmic complexity” to discuss the above questions.

This paper provides a framework enabling to define and determine the complexity of various universal programs for various machines. The approach consists of first defining the complexity as the average number of instructions to be executed by , when simulating the execution of one instruction of a program with input .

To obtain a complexity that does not depend on or , we then introduce the concept of an introspection coefficient expressing the average number of instructions executed by , for simulating the execution of one of its own instructions. We show how to obtain this coefficient by computing a square matrix whose elements are numbers of executed instructions when running selected parts of on selected data. The coefficient then becomes the greatest eigenvalue of the matrix.

We illustrate the approach using two examples of particularly efficient universal programs: one for a three-symbol Turing Machine (blank symbol not included) with an introspection coefficient of 3 672.98, the other for an indirect addressing arithmetic machine with an introspection coefficient of 26.27.

We discuss about two recent undecidability results in formal language theory. The corresponding problems are very simply formulated questions on finite sets of words. In particular, these results underline how finite sets of words can be used to perform powerful computations.

The classification of discrete dynamical systems that are computationally complete has recently drawn attention in light of Wolfram’s “Principle of Computational Equivalence”. We discuss a classification for cellular automata that is based on computably enumerable degrees. In this setting the full structure of the semilattice of the c.e. degrees is inherited by the cellular automata.

The theory of leaf language classes is a fruitful field of research which has been developed since the beginning of the nineties. The leaf language model, in which one language (or a pair of languages) defines a class of languages, allows a uniform definition and treatment of many complexity classes. The results of this area give new insights into the structure of complexity classes and their relation to other fields of Theoretical Computer Science.

P systems with active membranes using only two electrical charges and only rules of type i.e., evolution rules used in parallel in the regions of the membrane system, and of type i.e., communication rules sending out an object of a membrane thereby possibly changing the polarization of this membrane, assigned to at most two membranes are shown to be computationally complete, which improves the previous result of this type with respect to the number of polarizations as well as to the number of membranes. Allowing a special variant of rules of type to delete symbols by sending them out, even only one membrane is enough.

Reaction–diffusion models are commonly used to describe dynamical processes in complex physical, chemical and biological systems. Applications of these models range from pattern formation or epidemic spreads to natural selection through ecological systems and percolation systems. Reaction refers to phenomena where two or more entities become in contact and modify their state as a consequence of this fact. Diffusion implies the existence of a space where the involved entities are situated and can move. The Reaction–Diffusion Machine is a computational model we previously introduced inspired by reaction diffusion phenomena. In this work, we prove that a Deterministic Turing Machine can be simulated by a Reaction-Diffusion Machine.

Many different definitions of computational universality for various types of systems have flourished since Turing’s work. In this paper, we propose a general definition of universality that applies to arbitrary discrete time symbolic dynamical systems. For Turing machines and tag systems, our definition coincides with the usual notion of universality. It however yields a new definition for cellular automata and subshifts. Our definition is robust with respect to noise on the initial condition, which is a desirable feature for physical realizability.

We derive necessary conditions for universality. For instance, a universal system must have a sensitive point and a proper subsystem. We conjecture that universal systems have an infinite number of subsystems. We also discuss the thesis that computation should occur at the ‘edge of chaos’ and we exhibit a universal chaotic system.

Recently, functions over the reals that extend computable functions over the integers have been proved to correspond to the smallest class of real functions containing some basic functions and closed by composition and linear integration.

We extend this result to computable functions: functions over the reals that extend total recursive functions over the integers are proved to correspond to the smallest class of real functions containing some basic functions and closed by composition, linear integration and a very natural unique minimization schema.

We introduce a partial order on pictures (matrices), denoted by ≼ that extends to two dimensions the subword ordering on words. We investigate properties of special families of discrete sets (corresponding to {0,1}-matrices) with respect to this partial order. In particular we consider the families of polyominoes and convex polyominoes and the family, recently introduced by the authors, of L-convex polyominoes.

In the first part of the paper we study the closure properties of such families with respect to the order. In particular we obtain a new characterization of L-convex polyominoes: a discrete set is a L-convex polyomino if and only if all the elements  ≼  are polyominoes.

In the second part of the paper we investigate whether the partial orderings introduced are well-orderings. Since our order extends the subword ordering, which is a well-ordering (Higman’s theorem), the problem is whether there exists some extension of Higman’s theorem to two dimensions. A negative answer is given in the general case, and also if we restrict ourselves to polyominoes and even to convex polyominoes. However we prove that the restriction to the family of L-convex polyominoes is a well-ordering. This is a further result that shows the interest of the notion of L-convex polyomino.