Submitted works

Advanced search

math.DS — Dynamical Systems

Periodic Forcing, Echo Constraints and the Non-Periodicity of the Rule 30 Centre Column: Reductions, Structural Lemmas, Certified Computations and Barriers

Contributed by Isaac kaimfa

Wolfram's Rule 30 Prize Problem 1 asks whether the centre column of Rule 30, started from a single lit cell, is ever eventually periodic. We study the problem through a half-line system driven by a periodic boundary signal. Combining a known local identity with the standard reduction to finite seeds, Problem 1 follows from a single statement, the Echo Lemma: no finite half-line configuration driven by a non-constant periodic boundary can satisfy, at every lit boundary minute, the identity that Rule 30 forces on the neighbour of the centre. Around this formulation we prove a collection of exact structural results: a dependence-window lemma and a merging criterion for reconstructed columns, triangularity and monotonicity of the finite-support constraints, a forced-creation identity at boundary bounces, a description of the infinite survivors as a full shift for period two, and, for the two-sided period-two problem, uniqueness of the compatible left half together with exact forced identities near the centre, including a half-column that must vanish identically. For the linear relative Rule 150 we prove the analogue of the Echo Lemma for every odd period by a Frobenius self-similarity argument, and we identify exactly the two steps that fail for Rule 30. We report exhaustive and SAT-certified computations excluding counterexamples of bounded width, and we document a set of barriers: every exact mechanism found is confined to a bounded neighbourhood of the centre, no additive conserved quantity of small range exists, and the sideways reconstruction has a growing number of distinguishable states. The Echo Lemma, and with it Problem 1, remains open; the contribution of this article is a verified framework, labelled throughout as proved, certified or open.

A mix of human-written and AI-generated textHuman understanding: all partsRule 150Rule 30SAT certificatescellular automatacentre columneventual periodicityleft-permutive rules
Oct 27, 20265 pages
PDFView work

cs.CC — Computational Complexity

Generalized Bawo: A Finite-State Model and an EXPTIME Upper Bound

Contributed by Isaac kaimfa

Four-row mancala games, including Malawian Bawo and the related East African Bao, have received limited attention in computational complexity theory despite their combinatorial richness. This paper introduces GENERALIZED-BAWO-WIN, a finite-state two-player game model inspired by Malawian Bawo. The model is parameterized by a half-board width n and a binary-encoded lap cap L, and incorporates relay sowing, marker-pit capture, a formalized capture-relay rule (abstracting kichwa), mandatory capture, a singleton-start prohibition, and an explicit lap-cap truncation rule that guarantees move termination. We prove that GENERALIZED-BAWO-WIN belongs to EXPTIME under these semantics. The proof proceeds by establishing that the game's state space has size at most 2poly(|I|), that legal successors can be generated in 2poly(|I|) time, and that a WIN/LOSS/DRAW retrograde attractor can be computed over the resulting finite game graph. We emphasize that this is an upper bound: no hardness result is established. We further emphasize that the theorem applies only to the formally defined generalized model and does not classify Bao as played in East Africa, whose rules differ materially.

A mix of human-written and AI-generated textHuman understanding: all partsEXPTIMEcombinatorial gamescomputational complexityfinite gamesgeneralized Bawostate-space complexity
Sep 28, 202612 pages
PDFView work