Abstract Determining properties of an arbitrary binary sequence is a challenging task if only local processing is allowed. Among these properties, the determination of the parity of 1s by distributed consensus has been a recurring endeavour in the context of automata networks. In its most standard formulation, a one-dimensional cellular automaton rule should process any odd-sized cyclic configuration and lead the lattice to converge to the homogeneous fixed point of 0s if the parity of 1s is even and to the homogeneous fixed point of 1s, otherwise. The only proposed solution to this problem with a single rule was given more than 10 years ago (and coined BFO rule after the authors’ initials). However, three years later its authors realised that the rule would fail for a specific configuration and proposed a computationally sound fix, but a proof could not be worked out. Here we provide a fix to that failing rule along with a full proof, therefore reassuring that a single-rule solution to the problem really does exist.

The understanding of how predefined computations can be attained by means of individual cellular automata rules, their spatial arrangements or their temporal sequences, is a key conceptual underpinning in the general notion of emergent computation. In this context, here we construct a solution to the MOD n problem, which is the determination of whether the number of 1-bits in a cyclic binary string is perfectly divisible by the integer n > 1. Our solution is given for any lattice size N that is co-prime to n, and relies upon a set of one-dimensional rules, with maximum radius of n − 1, organised in a temporal sequence. Although the simpler cases of the problem for n = 2 and n = 3 have been addressed in the literature, this is the first account on the general case, for arbitrary n.

The Fourier spectra of one-dimensional cellular automata give a quantitative and qualitative characterisation of the average final configurations obtained out of their rules, as they are applied to sets of random initial configurations. The elementary cellular automata rule space presents spectra that bring to mind those of digital filters, and the same happens to some of the cellular automata rules obtained through composition of particular elementary cellular automata. As such, one might be willing to discover other filter type rules that might exist in larger spaces. In order to explore the possibility of detecting these cellular automata in a larger space, two methods are applied: a Multilayer Perceptron and the k-Nearest Neighbours classification algorithm. Both algorithms presented considerably high accuracies, with the Multilayer Perceptron showing an overall lower false negative rate, thus indicating that the methods may be generalised to other rule spaces and to the detection of other features, providing an automatic method to detect features in cellular automata spectra.

Standard practice for searching binary, one dimensional cellular automata rule space, relies on representing the candidate rule numbers by their corresponding binary sequence. Recently the use of ternary representation has been tried, which is based upon the traditional notion of schemata in genetic algorithms, though not with a focus on their effectiveness for the search. Here, we specifically go about such an evaluation, in the context of the classical benchmark task of density classification, in which the objective is to find a binary, one-dimensional rule that indicates the prevailing bit in a binary sequence, given to the rule as an initial configuration. The role of ternary representation is probed by comparing their introduction into two simple and traditional genetic algorithms of the literature, developed for the task. The experiments show that the ternary representation can lead to an increase in the number of high performance rules found for the task.

As part of the comprehensive theme of the relationships between dynamic systems and computational theories, a very active area of research has been the relationships between the generic dynamic behavior of Cellular Automata (CA) and their computational abilities. Various investigations have been carried out on the computational power of CA, with concentrated efforts in the study of one-dimensional CA and their computational abilities. One of the approaches is the use of Genetic Algorithms (GA) to look for CA with a predefined computational behavior. A set of parameters which we have previously shown to be effective in helping forecast CA dynamic behavior, are used here as an auxiliary metric to guide the GA search. To this end, we modified selection, mutation and crossover of a GA, so as to incorporate the heuristic, and obtained very effective results in the evolution search for CA that can solve the so-called synchronization task.

Cellular automata (CA) are important as prototypical, spatially extended, discrete dynamical systems. Because the problem of forecasting dynamic behavior of CA is undecidable, various parameter-based approximations have been developed to address the problem. Out of the analysis of the most important parameters available to this end we proposed some guidelines that should be followed when defining a parameter of that kind. Based upon the guidelines, new parameters were proposed and a set of five parameters was selected; two of them were drawn from the literature and three are new ones, defined here. This article presents all of them and makes their qualities evident. Then, two results are described, related to the use of the parameter set in the Elementary Rule Space: a phase transition diagram, and some general heuristics for forecasting the dynamics of one-dimensional CA. Finally, as an example of the application of the selected parameters in high cardinality spaces, results are presented from experiments involving the evolution of radius-3 CA in the Density Classification Task, and radius-2 CA in the Synchronization Task.

A new neural network model - the GasNet - has been recently reported in the literature, which, in addition to the traditional electric type, point-to-point communication between units, also uses communication through a diffilsable chemical modulator. Here we assess the applicability of this model in three different scenarios, the XOR problem, a food gathering task for a simulated robot, and a docking task for a virtual spaceship. All of them represent discrete domains, a contrast with the one where the GasNet was originally introduced, which had an essentially continuous nature. These scenarios are well-known benchmark problems from the literature and, since they exhibit varying degrees of complexity, they impose distinct performance demands on the GasNet. The experiments were primarily intended to better understand the model, by extending the original problem domain where GasNet was introduced. The results reported point at some difficulties with the current GasNet model.