Volume 18, Issue 3

In this paper we provide a computational method for evaluating the complexity of a large class of mathematical problems in a uniform way. The method, which is inspired by A New Kind of Science [1], is based on the possibility of completely describing complex mathematical problems, such as the Riemann hypothesis, in terms of very simple programs. The method is illustrated on a variety of examples from different areas of mathematics and its power and limits are studied.

Machi Zawidzki
Implementing Cellular Automata for Dynamically Shading a Building Facade

We present a practical cellular automaton (CA) implementation from the field of architecture that drives the modular shading system of a building facade. Some CAs produce patterns that seem to live their own life and may therefore please the human eye. Probably the most important quality of a good design is integrity of elements. By nature, a CA is an essence of integration, where all elements are interconnected and locally related to each other. Due to the computational irreducibility of CAs [1], controlling them to perform purposeful actions [2] is often challenging. Nevertheless, visual effects in the patterns created often develop intriguing complexity that is difficult to achieve by means of artistic will, whim, or chance. The four classes of CA behavior are presented with conjunction to the problem of average grayness of a pattern. Two CA classes are analyzed for potential practical use: 2-color, 1-dimension, range-1 (2C-1D-R1) and 2-color, 1-dimension, range-2 (2C-1D-R2). One problem discussed is the linear gradual change of average grayness as a function of the sequence of initial conditions. Another problem discussed is choosing a sequence of initial conditions to cause a desired change in the opacity of the shading array. A proposed realization includes a mechanical scheme that could be made inexpensively by using coupled polarized film. A rotation of one polarized film by 90 degrees causes a change in the element's transparency.

Edgar Delgado-Eckert
An Algebraic and Graph Theoretic Framework to Study Monomial Dynamical Systems over a Finite Field

A monomial dynamical system f : K^n→K^n over a finite field K is a nonlinear deterministic time discrete dynamical system with the property that each component function f_i : K^n→K is a monic nonzero monomial function. In this paper we provide an algebraic and graph theoretic framework to study the dynamic properties of monomial dynamical systems over a finite field. Within this framework, characterization theorems for fixed point systems, that is, systems in which all trajectories end in steady states, are proved. These characterizations are stated in terms of connectedness properties of the dependency graph. Our formalism allowed us to develop an algorithm of polynomial complexity for testing whether or not a given monomial dynamical system over an arbitrary finite field is a fixed point system. In addition, we were able to identify a class of monomial dynamical systems, namely, the (q-1)-fold redundant monomial systems. Within this class of systems a characterization of fixed point systems is proved that represents a generalization of previous work on Boolean monomial dynamical systems.

Christopher Stone (1), Larry Bull (2)
Solving the Density Classification Task Using Cellular Automaton 184 with Memory

A type of memory based on the least mean square algorithm is explored on the density classification task, which is a well-known test problem for two-state discrete dynamical systems. In the absence of memory, there is no elementary cellular automaton that can solve this task. However, when augmented with memory, the performance of elementary cellular automaton 184 approaches that of the best-known radius three cellular automata found in the literature. It is found that rule 184 transforms spatial information about the neighborhood into temporal information that memory is able to retain and present to the rule's transition function. This causes the cell to transition to a different state compared to the case when no memory is present, which extends blocks of cells having a common state to facilitate a solution of the task.

Genaro J. Martínez* (1, 2), Andrew Adamatzky (1), Ramon Alonso-Sanz (1), Juan C. Seck-Tuoh-Mora
Complex Dynamics Emerging in Rule 30 with Majority Memory

In cellular automata (CAs) with memory, the unchanged maps of conventional CAs are applied to cells endowed with memory of their past states in some specified interval. We implement the rule 30 automaton and show that by using the majority memory function we can transform the quasi-chaotic dynamics of classical rule 30 into domains of traveling structures with predictable behavior. We analyze morphological complexity of the automata and classify glider dynamics (particle, self-localizations) in the memory-enriched rule 30. Formal ways of encoding and classifying glider dynamics using de Bruijn diagrams, soliton reactions, and quasi-chemical representations are provided.

Eric S. Rowland
Regularity versus Complexity in the Binary Representation of 3^n

We use the grid consisting of bits of 3^n to motivate the definition of 2-adic numbers. Specifically, we exhibit diagonal stripes in the bits of 3^2^n, which turn out to be the first in an infinite sequence of such structures. Our observations are explained by a 2-adic power series, providing some regularity among the disorder in the bits of powers of 3. Generally, the base-p representation of k^p^n has these features.

Steve Seif
Constrained Eden

Let CA be a one-dimensional cellular automaton. A computational complexity problem, the Constrained Eden problem, denoted C-EDEN(CA), is introduced. C-EDEN(CA) is a finitary variant of the Garden of Eden problem. Even for certain elementary cellular automata, C-EDEN(CA) is NP-complete, providing the first examples of NP-complete problems associated with cellular automata over a two-element alphabet.