../..

Tag « cellular automata »

Study of the NP-completeness of the Compact Table

The problem of compact tables is to maximise the overlap when building a word that is to include permutations of every given words (all the words being the same length). This problem is shown to be NP-complete in the general case, and some specific restrictions are studied.

To show this on a small example (beyond what is in the article), imagine that in a game (like checkers) if blue takes red, on a result of 1, both are eliminated, on 2 or 3, red remains and blue remains in the other cases. If red takes blue, results 1 to 4 make red win and on 5 to 6, blue wins. The compact table in this case would be to keep the table as is in the blue versus red, add +2 if red versus blue, with results 7 and 8 letting red win.

lire la suite

Signals for Cellular Automata in Dimension 2 or Higher

In this article, co-written with Véronique Terrier for the Latin 2002 conference, we investigate how increasing the dimension of the array can help to draw signals on cellular automata. We show the existence of a gap of constructible signals in any dimension. We exhibit two cellular automata in dimension 2 to show that increasing the dimension allows to reduce the number of states required for some constructions.

lire la suite

The prefix notion in Kolmogorov complexity and computational models

Kolmogorov complexity theory gives a definition of randomness for words on a finite alphabet. The notions involved led to the description of a subclass of computable machines: the prefix computable machines, whose domain is a prefix code (no word in the domain is prefix of another one).

Beyond the matter of defining randomness for infinite words, this subclass has remarkable properties regarding computability theory. Three different definitions are given and compared. The case of comma free codes is also examined, but it doesn't yield anymore an additively optimal machine.
The notion of prefix also interacts with the computational models. An examination of machines with no blank characters or of finite models with an infinite calculus space (such as the Turing machine, which uses an infinite tape) reveals a strong influence of the prefix notion on computational processes.

lire la suite

Kolmogorov complexity and cellular automata classification

In this article, written jointly with Enrico Formenti and Bruno Durand, we present a new approach to cellular automata (CA) classification based on algorithmic complexity. We construct a parameter κ which is based only on the transition table of CA and measures the "randomness" of evolutions; κ is better, in a certain sense, than any other parameter recursively definable on CA tables. We investigate the relations between the classical topological approach and ours one. Our parameter is compared with Langton's λ parameter: κ turns out to be theoretically better and also agrees with some practical evidences reported in literature. Finally, we propose a protocol to approximate κ and make experiments on CA dynamical behavior.

lire la suite