27 August 2023 - James Wiles

Problem:

DOES COMPUTING THE NTH CELL OF THE CENTER COLUMN REQUIRE AT LEAST O(N) COMPUTATIONAL EFFORT? [5]

Abstract:

This research paper explores the emergence of predictable triangle patterns within Rule 30's evolution and examines its potential implications on computational efficiency. By identifying and characterising these patterns, the study seeks to understand scenarios where the standard computational effort might be reduced, albeit conditionally. While the established perception posits an O(N) computational effort for the nth cell of Rule 30, the findings in this paper highlight instances where this might be temporarily bypassed.

Introduction:

Rule 30, a one-dimensional cellular automaton introduced by Stephen Wolfram, has long been an archetype of complex behaviour arising from simple rules. Its evolution poses intriguing questions on predictability and computational irreducibility [3]. This research aims to shed light on specific patterns that emerge within Rule 30's chaotic behaviour and the potential to predict subsequent evolutions, at least conditionally. By identifying and formalising these patterns, we aim to show that it is possible to compute some nth cells with less than O(N) computation.

Methodology:

  1. Pattern Recognition: A rigorous examination of Rule 30's evolution was undertaken to identify recurring patterns [2]. Special attention was given to patterns leading to deterministic behaviour in subsequent rows. Additional attention was given to patterns overlaying the centre column.
  2. Computational Efficiency Analysis: For each recognized pattern, an evaluation was carried out to determine the potential computational savings. The time complexity in the presence and absence of these patterns was assessed.
  3. Computation and Composition Tools: Extraction of Rule 30 sequences and validation of thought processes were done using OpenAI’s ChatGPT GPT-4 Code Interpreter August 3 Version.
  4. Validation of Sequences: Rule 30 sequence validation was done using the Rule 30 Wikipedia entry [4].

Observations:

  1. The Emergent Triangle Pattern: When an initiating line, composed exclusively of 3 or more white/blank cells (represented by 0's), is observed, a triangle structure predictably forms. This "emergent triangle," exhibits deterministic formation and evolution. This allows for anticipation of certain cell states within the pattern without processing the preceding cells.

Rule 30 up to to row 30 showing the emergent triangles of different lengths

Rule 30 up to to row 30 showing the emergent triangles of different lengths

  1. Prediction Length: Predicting rows beyond the immediate next iteration becomes feasible for initiating lines with a length greater than 2 cells. The emergent triangle is always enveloped by one additional predictive cell. This cell can be either 1 or 0, determined by whether the initiating line contains an even or odd number of cells.

Emergent triangles with initiating cell line lengths 3, 4, 5, and 6 respectively

Emergent triangles with initiating cell line lengths 3, 4, 5, and 6 respectively

  1. Significant Emergent Pattern: The first non-trivial prediction for the centre column can be found starting from row 7. At this row, an emergent triangle forms from an initiating line with a length of 4 cells, with the centre column situated on the second cell of the initiating line. This configuration allows for the prediction of the centre column's outcome for 2 iterations. A more significant prediction emerges on row 105, offering predictions for 3 iterations.

Patterns emerging over the centre column on row 7 and row 105 respectively

Patterns emerging over the centre column on row 7 and row 105 respectively

  1. Positional Predictability: For a cell at position p in an initiating line of length L the number of predictable rows R: