Rule 110

This article includes a list of general references , but it lacks sufficient corresponding inline citations . Please help to improve this article by introducing more precise citations. (November 2012) ( Learn how and when to remove this message )

The Rule 110 cellular automaton (often referred to with a weary sigh as simply Rule 110, as if its complexity were an imposition) is an elementary cellular automaton that exhibits a fascinating, if somewhat exhausting, complexity. Its behavior resides precisely on the precarious boundary between predictable stability and outright chaos. In this regard, it shares a certain unsettling kinship with Conway’s Game of Life , another system where simple rules beget emergent, intricate patterns. What truly elevates Rule 110 from a mere curiosity to a profound enigma is the discovery that, when configured with a specific, carefully crafted repeating background pattern, it is demonstrably Turing complete . This isn’t just a trivial observation; it’s a declaration that, in principle, any conceivable calculation or computer program could be simulated within the confines of this deceptively simple automaton. It means the universe, in some abstract sense, could run on a few binary rules and a dash of cosmic indifference.

An example run of the rule 110 cellular automaton over 256 iterations, starting from a single cell. Observe the patterns; they’re not random, merely chaotic enough to be interesting.

Definition

In the realm of an elementary cellular automaton , one observes a one-dimensional arrangement of binary states—0s and 1s—which undergoes evolution through a rudimentary, yet profoundly impactful, set of rules. The determination of whether a particular cell within this linear pattern will assume a state of 0 or 1 in the subsequent generation is entirely contingent upon its current value, along with the values of its immediate two neighbors. It’s a localized democracy, where only the closest opinions matter.

An animation of the way the rules of a 1D cellular automaton determine the next generation, using Rule 110. Pay attention, it’s not rocket science, but apparently, it’s universal.

The Rule 110 automaton, in its elegant simplicity, operates according to the following prescriptive set of transformations, dictating the fate of each central cell:

The designation “Rule 110” is not some arbitrary, whimsical label, but rather a direct consequence of its underlying binary representation . This specific rule set can be succinctly encapsulated by the binary sequence 01101110. When this binary string is interpreted as a conventional binary number , it yields the decimal value 110. This systematic nomenclature is a hallmark of the Wolfram code naming scheme, a method established by Stephen Wolfram to uniquely identify and categorize the vast landscape of elementary cellular automata based on their rule tables. It’s a rather efficient way to name things, assuming you’re comfortable with converting binary to decimal, which, judging by some inquiries, is not a given.

History

The pivotal moment in the history of Rule 110 arrived in 2004, when Matthew Cook finally published his long-anticipated proof demonstrating that Rule 110, specifically when operating within a meticulously designed, repeating background pattern, achieves Turing completeness . This means it is capable of universal computation —a computational model that can simulate any other computational model. This profound assertion was not a sudden revelation; it was the culmination of a conjecture initially put forth by Stephen Wolfram way back in 1985. The journey to this publication, however, was far from straightforward, tinged with intellectual property disputes and legal wrangling.

Cook had actually presented the core of his groundbreaking proof at the Santa Fe Institute conference CA98, long before the public release of Wolfram’s monumental work, A New Kind of Science . This chronological precedence inadvertently triggered a rather unpleasant legal affair, rooted in a non-disclosure agreement Cook had signed with Wolfram Research , his employer at the time. The implication was that Cook’s presentation, and subsequent attempts to publish, might have violated the terms of this agreement, given the proprietary nature of Wolfram’s ongoing research into cellular automata.

Consequently, Wolfram Research took measures to impede the dissemination of Cook’s proof, effectively blocking its formal publication for several years. This created a peculiar situation where a significant scientific discovery was known within a specific academic circle but remained officially unconfirmed in the wider scientific literature. The controversy highlighted the often-tense intersection of academic freedom, corporate intellectual property, and the pursuit of fundamental scientific understanding. It’s almost as if some people care more about who says it first than what’s actually being said.

Interesting properties

Among the 88 possible unique elementary cellular automata —a surprisingly small number for such profound implications, if you ask me—Rule 110 stands as a singular achievement. It is the only one for which Turing completeness has been directly and rigorously proven. While proofs for several closely related rules (such as Rule 124, which is merely the horizontal reflection of Rule 110, a detail that hardly warrants a separate celebration) follow as straightforward corollaries, Rule 110 remains the archetypal example. Its elegant simplicity, coupled with its immense computational power, has led many to describe Rule 110 as one of the simplest known Turing complete systems. It’s a testament to how complex behavior can emerge from the most minimalist of rules, a concept that frankly, some humans could learn from.

Rule 110, much like its more famous cousin, the Game of Life , conspicuously exhibits what Wolfram himself categorized as “Class 4 behavior.” This classification describes systems that are neither entirely stable, settling into static or simple periodic patterns, nor are they completely chaotic, devolving into unpredictable, random noise. Instead, Class 4 automata are characterized by the emergence of localized, persistent structures—often referred to as “spaceships” or “gliders”—that appear, move, collide, and interact in astonishingly complex and non-trivial ways. These interactions are not mere statistical fluctuations; they are the very substrate upon which computation can be built, providing the necessary complexity for information processing.

Matthew Cook ’s seminal proof of Rule 110’s capacity for universal computation was a masterful display of reduction. He meticulously demonstrated this by successively emulating a hierarchy of computational models. First, he showed how Rule 110 could emulate cyclic tag systems , a somewhat obscure but powerful computational model. From there, he progressed to demonstrating the emulation of 2-tag systems , which are known to be universal. The final, crucial step involved showing how 2-tag systems, and thus Rule 110, could in turn emulate full-fledged Turing machines . This final stage, while conclusive, came with a significant practical caveat: the emulation of the Turing machine’s tape, encoded using a unary numeral system , incurred an exponential time overhead. This means that while theoretically universal, the practical speed of such an emulation would be rather sluggish, to put it mildly.

However, the field of computational complexity rarely rests on its laurels. Neary and Woods, in their 2006 work, presented an alternative construction that aimed for greater efficiency. Their approach ingeniously replaced the 2-tag systems with “clockwise Turing machines,” resulting in a proof with a more palatable polynomial overhead. This improvement, while perhaps less dramatic than the initial discovery of universality, significantly enhanced the theoretical efficiency of Rule 110 as a computational engine, making it slightly less cosmically frustrating to consider.

The proof of universality

The narrative surrounding Matthew Cook ’s proof of the universality of Rule 110 is as much a tale of scientific discovery as it is one of academic and legal friction. As previously noted, Cook initially presented the foundational elements of his proof at a Santa Fe Institute conference. The timing of this presentation, occurring prior to the widely anticipated publication of A New Kind of Science by Stephen Wolfram , became a point of contention. Wolfram Research subsequently asserted that Cook’s presentation constituted a breach of his nondisclosure agreement with them. This claim led to a court order that effectively barred Cook’s paper from being included in the official published proceedings of the conference. Despite these legal maneuvers and the temporary suppression of formal publication, the existence of Cook’s groundbreaking proof became known within the academic community, an inconvenient truth that refused to be silenced.

The significant interest generated by Cook’s proof extended beyond the mere affirmation of Rule 110’s universality. It also stemmed from the intricate and highly technical details of his construction, which offered a fresh perspective on the capabilities of such elementary systems. The character of Cook’s rigorous, step-by-step mathematical proof diverged considerably from the more expansive, philosophical, and observational discussion of Rule 110 presented in A New Kind of Science . Cook, undeterred by the earlier obstacles, eventually authored a comprehensive paper meticulously outlining his complete proof, ensuring its proper place in the scientific record.

Cook’s methodology for demonstrating Rule 110’s universality (or Turing completeness ) was a masterclass in computational reduction. He achieved this by showing that it was indeed possible to configure the rule to emulate another known universal computational model: the cyclic tag system . This approach required a meticulous deconstruction of Rule 110’s emergent properties. His first critical step involved the identification and isolation of various " spaceships "—self-perpetuating, localized patterns that could traverse the cellular automaton’s lattice without dissipating. These dynamic entities were observed to exist and persist within an infinitely repeating background pattern in a Rule 110 universe. Once these fundamental moving parts were identified, Cook then ingeniously devised a system whereby specific combinations of these structures could be made to interact in a precisely controlled manner. This intricate choreography of collisions and transformations formed the operational basis that could then be exploited for the purposes of computation, essentially building a complex machine out of simple, moving pixels.

Spaceships in Rule 110

The very foundation of a universal machine constructed within Rule 110 hinges upon the ability to embed a finite, yet carefully orchestrated, number of localized patterns within an infinitely repeating background pattern. This background, a stable and recurrent “ether” if you will, is precisely fourteen cells wide, and it cycles through its exact configuration every seven iterations. The specific binary sequence that defines this foundational pattern is 00010011011111. It’s the stage upon which all the computational drama unfolds, and it repeats with the relentless precision of a forgotten cosmic clock.

Within this repeating backdrop, three distinct localized patterns hold particular significance in the intricate machinery of the Rule 110 universal computer. These crucial structures are visually presented in the accompanying image, each gracefully enveloped by the ubiquitous repeating background pattern.

In these illustrative figures, time progresses in a downward direction: the uppermost line invariably represents the initial, pristine state, while each subsequent line meticulously depicts the state of the automaton at the very next temporal iteration. It’s a snapshot of a fleeting moment, stretched into a visual history.

The leftmost structure depicted is a dynamic entity that exhibits a consistent translation: it shifts two cells to the right and precisely repeats its internal configuration every three generations. This “glider” is fundamentally comprised of the binary sequence 0001110111, meticulously framed by the aforementioned repeating background pattern. Furthermore, its definition encompasses two distinct, yet consistent, evolutions of this core sequence, demonstrating its self-perpetuating nature as it moves across the cellular landscape. It’s a small, persistent ripple in the fabric of the automaton.

The central structure is another mobile pattern, but one that travels with a different rhythm. This particular spaceship shifts eight cells to the left, completing its internal cycle and repeating its exact form every thirty generations. Its core composition is the binary sequence 1001111, again meticulously bordered by the standard background pattern. However, due to its longer cycle, its definition inherently includes twenty-nine distinct evolutionary stages of this sequence, illustrating the complex internal dynamics that allow it to maintain its integrity while traversing the grid.

Finally, the rightmost structure offers a contrast in its behavior. Unlike its mobile counterparts, this pattern remains resolutely stationary, anchored to its position. It repeats its internal configuration every seven generations, providing a stable, localized presence. This static “block” is composed of the simple binary sequence 111, and its definition includes five different evolutionary steps within its seven-generation cycle, all while maintaining its fixed spatial coordinates. It’s the unmoving reference point in a world of constant flux.

Below is an image showcasing the elegant interplay of these fundamental structures. On the left, one can observe the first two structures—the right-shifting and left-shifting spaceships —passing through each other with remarkable indifference, their only interaction being a temporary superposition that resolves back into their original, translated forms. It’s a testament to the robust nature of these patterns. On the right, however, the image reveals a more profound interaction: the collision of these two dynamic entities resulting in the formation of the third, stationary structure. This demonstrates that these aren’t just isolated curiosities; they are the fundamental components of a logic gate, capable of transforming information through their interactions.

There are, naturally, a multitude of other spaceships and localized patterns that manifest within Rule 110. The universe of this automaton is rich with emergent complexity. However, for the specific and demanding task of proving its Turing completeness , these three particular structures—the right-moving glider, the left-moving glider, and the stationary block—play the most prominent and indispensable roles in the universality proof. The others are merely background noise, or perhaps, future research.

Constructing the cyclic tag system

The intricate machinery necessary to reconstruct a cyclic tag system within the environment of Rule 110 is composed of three primary, meticulously synchronized components. To call it “machinery” is almost too generous, given it’s just bits flipping, but the functional elegance is undeniable:

• A data string which is stationary; This acts as the memory, the current state of computation.
• An infinitely repeating series of finite production rules which start on the right and move leftward; These are the instructions, the program that dictates how the data string evolves.
• An infinitely repeating series of clock pulses which start on the left and move rightward. These pulses provide the timing, the rhythmic beat that synchronizes the entire operation and facilitates transformations.

The initial spatial arrangement, the precise spacing between these components, is not merely important; it is of utmost importance. If you get it wrong, the whole thing collapses into meaningless noise. For the cellular automaton to faithfully implement the cyclic tag system , the automaton’s initial conditions must be selected with an almost surgical precision. This ensures that the myriad localized structures embedded within—our aforementioned spaceships and stationary blocks—interact in a highly ordered, predictable, and computationally meaningful way. It’s a delicate balance, easily disrupted by a single misplaced bit.

The “data string” of the cyclic tag system is represented by a sequence of the stationary repeating structures previously described. These aren’t just decorative; they encode information. The critical distinction between a ‘1’ symbol and a ‘0’ symbol in the data string is conveyed by varying amounts of horizontal space separating these stationary structures. This string, representing the “word” upon which the cyclic tag system operates, undergoes a fundamental transformation with each computational step: the very first symbol in this string is invariably “destroyed” upon the consideration of every incoming production rule. The subsequent behavior of the system hinges entirely on the value of this destroyed leading symbol. If the leading symbol was a ‘1’, new symbols are appended to the end of the data string. If, however, it was a ‘0’, no new symbols are added. This simple conditional branching is the essence of the tag system’s logic.

From the right side of this computational arena, a continuous stream of left-moving structures (specifically, the left-shifting spaceships ) enters. These structures, much like the data string, are separated by varying amounts of horizontal space. These spacings encode the ‘0’s and ‘1’s that constitute the cyclic tag system ’s “production rules.” Since the tag system’s production rules are pre-defined at the inception of the program and are, by definition, infinitely repeating, their patterns of ‘0’s and ‘1’s can be meticulously represented by an infinitely repeating string within the automaton’s initial condition . Each distinct production rule within this infinite sequence is demarcated from the next by a specialized structure known as a “rule separator” (or sometimes, a “block separator”). These separators also move towards the left, maintaining a precise, synchronized pace with the encoding of the production rules themselves.

When one of these left-moving rule separators encounters a stationary symbol within the cyclic tag system ’s data string, its primary action is to cause the immediate destruction of that first symbol it encounters. However, its subsequent behavior diverges critically based on the value of the symbol it just annihilated. If the symbol encoded by the string was a ‘0’, the rule separator undergoes a transformation, changing into a new structure. This new structure’s purpose is to act as a barrier, effectively blocking the incoming production rule from having any effect. This temporary blocking structure is then itself destroyed when it inevitably encounters the next rule separator, clearing the path for the subsequent computational cycle.

If, on the other hand, the symbol within the string was a ‘1’, the rule separator transforms into a different kind of new structure. This particular transformation serves to admit the incoming production rule, allowing its encoded instructions to proceed. While this new, permissive structure is also eventually destroyed upon collision with the subsequent rule separator, it first fulfills its crucial role by allowing a series of structures—representing the new symbols to be appended—to pass through towards the left. These passing structures are then meticulously guided to append themselves to the trailing end of the cyclic tag system ’s data string. This final, critical transformation, the actual appending of new symbols, is achieved through the precise interaction with a series of infinitely repeating, right-moving “clock pulses.” These pulses, manifesting as the right-moving patterns previously described, are the agents of change. They effectively transform incoming left-moving ‘1’ symbols from a production rule into stationary ‘1’ symbols within the data string, and similarly convert incoming ‘0’ symbols from a production rule into stationary ‘0’ symbols of the data string. It’s a ballet of bits, orchestrated to perform computation.

Cyclic tag system working

The figure above, a rather stark schematic diagram, represents the conceptual blueprint for the reconstruction of a cyclic tag system within the specific, constrained universe of Rule 110. It is a visual distillation of the complex interplay of localized patterns, moving information, and precisely timed interactions that collectively enable universal computation within this elementary cellular automaton. It illustrates how the abstract rules of a tag system are concretely mapped onto the dynamic, emergent behavior of a simple, one-dimensional binary grid. If you squint hard enough, you might even see the universe itself in there.

See also

• Rule 30
• Rule 90
• Rule 184

Notes

• ^ 110 is the number 110 , written in conventional decimal notation, and thus is pronounced as one pronounces nominal numbers ordinarily. For example, Stephen Wolfram pronounces the name “rule one-ten”. This isn’t groundbreaking, just clarifying for those who might overthink it.