Shift-symmetric configurations in two-dimensional cellular automata: Irreversibility, insolvability, and enumeration

in Chaos (2019), 29(6), 063120

The search for symmetry as an unusual yet profoundly appealing phenomenon, and the origin of regular, repeating configuration patterns have long been a central focus of complexity science and physics. To ... [more ▼]

The search for symmetry as an unusual yet profoundly appealing phenomenon, and the origin of regular, repeating configuration patterns have long been a central focus of complexity science and physics. To better grasp and understand symmetry of configurations in decentralized toroidal architectures, we employ group-theoretic methods, which allow us to identify and enumerate these inputs, and argue about irreversible system behaviors with undesired effects on many computational problems. The concept of so-called configuration shift-symmetry is applied to two-dimensional cellular automata as an ideal model of computation. Regardless of the transition function, the results show the universal insolvability of crucial distributed tasks, such as leader election, pattern recognition, hashing, and encryption. By using compact enumeration formulas and bounding the number of shift-symmetric configurations for a given lattice size, we efficiently calculate the probability of a configuration being shift-symmetric for a uniform or density-uniform distribution. Further, we devise an algorithm detecting the presence of shift-symmetry in a configuration. Given the resource constraints, the enumeration and probability formulas can directly help to lower the minimal expected error and provide recommendations for system’s size and initialization. Besides cellular automata, the shift-symmetry analysis can be used to study the non-linear behavior in various synchronous rule-based systems that include inference engines, Boolean networks, neural networks, and systolic arrays. [less ▲]

Modeling the complex dynamics of enzyme-pathway coevolution.

in Chaos (2010), 20(4), 045115

Metabolic pathways must have coevolved with the corresponding enzyme gene sequences. However, the evolutionary dynamics ensuing from the interplay between metabolic networks and genomes is still poorly ... [more ▼]

Metabolic pathways must have coevolved with the corresponding enzyme gene sequences. However, the evolutionary dynamics ensuing from the interplay between metabolic networks and genomes is still poorly understood. Here, we present a computational model that generates putative evolutionary walks on the metabolic network using a parallel evolution of metabolic reactions and their catalyzing enzymes. Starting from an initial set of compounds and enzymes, we expand the metabolic network iteratively by adding new enzymes with a probability that depends on their sequence-based similarity to already present enzymes. Thus, we obtain simulated time courses of chemical evolution in which we can monitor the appearance of new metabolites, enzyme sequences, or even entire organisms. We observe that new enzymes do not appear gradually but rather in clusters which correspond to enzyme classes. A comparison with Brownian motion dynamics indicates that our system displays biased random walks similar to diffusion on the metabolic network with long-range correlations. This suggests that a quantitative molecular principle may underlie the appearance of punctuated equilibrium dynamics, whereby enzymes occur in bursts rather than by phyletic gradualism. Moreover, the simulated time courses lead to a putative time-order of enzyme and organism appearance. Among the patterns we detect in these evolutionary trends is a significant correlation between the time of appearance and their enzyme repertoire size. Hence, our approach to metabolic evolution may help understand the rise in complexity at the biochemical and genomic levels. [less ▲]