Introduction: The Computational Universe and the Paradox of Simple Rules

Traditional scientific intuition has relied on the assumption that systems exhibiting complex behavior must be grounded in correspondingly complex underlying rules. However, the development of computational experiments that began in the latter half of the twentieth century, and especially Stephen Wolfram’s presentation of A New Kind of Science (NKS), fundamentally overturned this paradigm1. Research into cellular automata (CA) revealed that extremely simple deterministic rules can generate structures that appear random and unpredictably complex. This phenomenon is not a special case limited to CA, but is highly likely to be a universal property inherent in the very concept of computation itself2.

This report comprehensively examines a range of simple computational systems other than cellular automata, including mobile automata, Turing machines, substitution systems, tag systems, and register machines, and analyzes the processes through which complexity emerges across their formal differences. It also discusses how the behaviors exhibited by these systems converge toward the unifying concept of the “Principle of Computational Equivalence,” and presents a decisive answer to the question of whether complexity is a universal phenomenon.

Mobile Automata: Locality of Updating and Mechanisms of Information Propagation

Mobile automata (MA) are discrete computational models similar to cellular automata, but they are characterized by the elimination of “parallelism” in the information updating process and by the radical pursuit of “sequentiality”4. Whereas in CA all cells in a lattice are updated simultaneously at each step, in MA only a single “active cell” is updated at any given time, and this active point moves through space according to the rule4.

Formal Definition and Operation of Mobile Automata

A mobile automaton consists of a one-dimensional row of cells with states, or colors, and an active scanner that indicates a specific position within that row. At each step, the system transitions according to the following rules.

  1. It refers to the states of the current active cell and its left and right neighboring cells4.
  2. Based on the rule, it determines the new color of the active cell6.
  3. Based on the rule, it moves the active scanner to the left, to the right, or keeps it in place4.

In MA with two states, there are 65,536 possible rules that refer to this local neighborhood4. When this vast rule space is explored comprehensively, a hierarchy of behaviors similar to that observed in CA can be found.

Classification of behavior Characteristics of spatial patterns Level of complexity
Stationary or repetitive type The active cell remains within a narrow range and follows a simple periodic trajectory4. Low, corresponding to Class 1 or 2
Nested type The active cell regularly moves back and forth while expanding its range, forming self-similar patterns6. Medium, fractal structure
Complex or random type Even when the movement of the active cell appears regular, the distribution of colors left in the background becomes statistically random6. High, corresponding to Class 3 or 4

###

The Rarity of Complexity and Generalized Mobile Automata

What deserves attention is that, in mobile automata, the frequency with which rules produce “complex behavior” is significantly lower than in cellular automata6. In MA, most rules converge toward simple repetition or nested structures, while rules that generate chaotic or complex patterns amount to less than a few percent6. This is because information updating is restricted to a single point, making it difficult for information to diffuse and interfere.

The “generalized mobile automaton” was devised to relax this constraint. In this model, multiple active cells are allowed to exist simultaneously, and active cells may split or disappear depending on conditions6. As the number of active cells increases and the system’s capacity for parallel information processing rises, its behavior rapidly approaches that of cellular automata, and the rate at which complex patterns appear increases dramatically6. This fact suggests that “parallelism of information” is advantageous for the emergence of complexity, while also showing that even MA, a sequential system constrained to the extreme, can still generate complex behavior if an appropriate rule is selected5.

Turing Machines: The Minimal Unit of Computation and the Limit of Universality

The Turing machine (TM), an emblem of computation theory, is also a typical example of a system that produces complex behavior from simple rules. In NKS, Wolfram reinterpreted the TM not as an abstract mathematical tool, but as a physical dynamical system, and pursued universality in its “minimal configuration”7.

The Search for the Smallest Universal Turing Machine

The search for the “smallest universal Turing machine,” proposed by Claude Shannon in 1956, has long been a major problem in computer science7. It was generally thought that achieving universality required a complex state transition diagram, but Wolfram predicted that a 2-state, 3-symbol (2,3) Turing machine might be universal7. In 2007, Alex Smith proved the universality of this machine, confirming that its rule set consists of only six instructions, corresponding to combinations of states and symbols7.

State-symbol pair (m, n) Physical complexity (mn) Notes
(15, 2\) 30 Standard universal machine by Rogozhin8
(4, 6\) 24 Efficient 22-instruction machine by Rogozhin10
(2, 3\) 6 Smallest universal machine proven by Smith7
(2, 4\) 8 Efficient universal machine by Woods and Neary11

Weak Universality and the Encoding of Information

What became controversial in the proof of the (2,3) machine was the definition of the initial condition. A standard universal Turing machine must begin with a tape that is blank except for a finite input, but the (2,3) machine proven by Smith is based on “weak universality,” which allows specific repeating patterns to exist on both ends of the tape7. Critics argue that this embeds complexity into the initial condition. From the standpoint of the Principle of Computational Equivalence, however, as long as the process of constructing the initial condition itself does not contain universal computation, the computational capability of the system itself is considered essential2.

The fact that such a minimal system can possess universality shows that computational power is not necessarily produced by a particular advanced design, but is “ubiquitous” within chains of simple interactions. This suggests that physical phenomena at the molecular level may themselves be carrying out advanced computation7.

Substitution Systems and Geometric Fractals: Rule Independence and the Effects of Interference

Substitution systems are systems in which components are replaced by collections of other components according to rules, and they form the foundation of fractal geometry12. The behavior of such systems is decisively divided according to whether substitution operations are performed independently on each element, or whether they involve “interference” with neighboring elements12.

Neighborhood-Independent Substitution Systems and the Inevitability of Nested Structures

In the simplest forms of substitution systems, namely independent 1D and 2D substitution systems, each element is replaced at each step by a fixed set of multiple elements. Because this process does not depend on the “state of the neighborhood,” the patterns generated inevitably become highly regular “nested” structures12.

  • Example: The Sierpiński gasket is a typical self-similar figure generated by a two-dimensional substitution system14.
  • Growth rate: The increase in the number of elements in these systems can be described by linear recurrence, such as the Fibonacci sequence, and their behavior is completely predictable13.

The Explosion of Complexity in Sequential Substitution Systems

Informational complexity appears when “order” or “interference” is introduced into the rules of substitution. The “sequential substitution systems” proposed by Wolfram scan an entire string and replace only the first occurrence of a particular pattern that is found17.

Studies show that merely introducing this “sequentiality” allows the behavior to escape fractal regularity and exhibit random complexity18.

  • Frequency: Among randomly selected rules, roughly one in 10,000 produces statistically random and unpredictable patterns19.
  • Significance: This shows that the “order of updating” has a decisive influence on the behavior of the entire system. It also proves that even simple string operations can possess computational capabilities equivalent to cellular automata if appropriate competitive conditions arise17.

Tag Systems: The Integration of Number-Theoretic Intuition and Computational Universality

Tag systems, introduced by Emil Post in 1943, are extremely simple systems that delete the beginning of a string and append characters to the end according to that content20. Although this model has the intuitive form of string transformation, it is known for its connection to deep problems in computation theory, especially the Collatz conjecture21.

The Structure and Universality of 2-Tag Systems

The rules of a tag system are defined by the deletion number () and a set consisting of an alphabet and production rules. “2-tag systems,” whose deletion number is 2, were once historically thought incapable of producing complex behavior. Yet Post himself encountered their unpredictability and ultimately abandoned the attempt to resolve the problem20.

  • Proof of universality: In the 1960s, Minsky showed that 2-tag systems can simulate Turing machines, thereby proving their universality21.
  • Efficiency: According to recent research by Woods, Neary, and others, 2-tag systems can efficiently simulate the computations of Turing machines in polynomial time. This means that many “small universal machines” are, despite appearances, powerful computational resources23.

Representation of the Collatz Conjecture by Tag Systems

What symbolizes the complexity of tag systems is the simulation of the difficult number-theoretic problem known as the problem. The 2-tag system shown by De Mol (2008) and others carries out Collatz iteration by converting it into string length21.

Production rules of the 2-tag system Number-theoretic meaning
A flag for guiding the value of into the process of 21.
Represents the operation of as deletion from a string21.
Represents amplification of a value as addition to a string21.

In this system, when starting from the initial string 'aaa' (n=3), the string repeatedly undergoes unpredictable expansion and convergence before eventually halting, meaning that the value reaches 1. This behavior shows that the simple form of a tag system contains within it advanced mathematical truths that humanity has not yet fully clarified21.

Register Machines and FRACTRAN: The Extreme of Arithmetic Minimalism

Register machines are abstract models of modern computers that operate on integers stored in a small number of registers25. This system consists only of two basic instructions, “addition” and “conditional subtraction,” meaning subtract and jump if not zero. Despite its simplicity, it is no less capable than other systems in terms of the emergence of complexity.

Universality with Two Registers

Marvin Minsky proved that a machine with only two registers can be universal, or Turing complete26. The core of this proof lies in an elegant method: encoding the states of multiple virtual registers as exponents in a single integer , and manipulating them by using the uniqueness of prime factorization28.

  • Substitution of instructions: Addition instructions correspond to multiplication by specific prime numbers, and subtraction instructions correspond to division26.
  • Conclusion: This shows that even when the number of physical registers is minimal, namely two, there is no limit to the content of computation28.

FRACTRAN: Programs Made Only of Fraction Multiplication

FRACTRAN, invented by John Conway, is a system that abstracts the concept of register machines to its limit. A FRACTRAN program is simply a “list of fractions.” For the current number , the program tries multiplying it by fractions from the beginning of the list, selects the first fraction for which “the result is an integer,” and updates 29.

Conway’s “PRIMEGAME” generates a sequence of prime numbers using only a list of 14 fractions29.

When powers of , namely , appear in this sequence, their exponents are always prime numbers29. FRACTRAN proves that even when the syntax of a programming language is stripped down to the basic arithmetic operations of multiplication and division, the capacity to describe advanced algorithms remains fully intact31.

The Principle of Computational Equivalence (PCE): A Law of Universal Computational Capability

As we have seen, systems with different forms and different objects of operation, such as CA, MA, TM, tag systems, register machines, and substitution systems, all produce “complex behavior from simple rules” and even acquire “universal computational capability.” Based on this broad empirical fact, Wolfram proposed the “Principle of Computational Equivalence” (PCE)33.

The Core Claims of the Principle

The Principle of Computational Equivalence presents three essential insights into the computational universe.

  1. Every process is computation: Physical phenomena in nature, human thought, and simple computer programs can all be equally defined as computational processes that transform inputs into outputs33.
  2. A ceiling of sophistication: Unless the rules of a system are extremely simple, they all perform computations of “equivalent sophistication.” There is not a continuous hierarchy of sophistication. Rather, once a certain threshold is crossed, the system immediately reaches the “maximum level,” namely universality33.
  3. The ubiquity of universality: Universality, once thought to be the product of special and advanced design, is in fact a universal attribute found throughout the computational universe33.

A Challenge to Traditional Science

PCE reveals the limits of the “predictability” on which traditional science has relied. If a system possesses universal computational capability, predicting its future state requires an amount of effort equivalent to the computation performed by the system itself35. This is “computational irreducibility”37.

Scientific approach Characteristics Limitations
Traditional mathematics and physics The pursuit of “shortcuts” through equations35. Applicable only to linear and reducible systems19.
NKS and computational science Step-by-step simulation and observation2. For predicting irreducible behavior, the execution of the computation is necessary37.

What this principle suggests is that the computational capability of us as observers, namely humans, cannot “exceed” the computational capability of the observed object, namely the processes of nature35. Therefore, even if simple rules can be discovered behind complex phenomena, this does not necessarily mean that their outcomes can be “foreseen.”

Discussion: Complexity and Computation as Universal Phenomena

This study has shown that the phenomenon in which complex behavior emerges from simple rules is a “universal phenomenon” that does not depend on the form of computation, such as data structures or methods of updating.

Why Does Complexity Arise?

The common keys to the emergence of complexity are “conflict” between rules and “feedback” of information.

  • In mobile automata, the movement of the active cell and the changing of colors form a spatial history, which then constrains the future behavior of the active cell4.
  • In tag systems, the time-displaced operations of deleting from the beginning and appending to the end generate irregular interference of information20.
  • In register machines, arithmetic relations involving increases and decreases of exponents embed advanced logical operations into the structure of prime factorization26.

All of these arise from the fact that the system has a recursive structure in which it “refers to its own past state and incorporates it into future decisions”2.

Criticism of Universality and Responses

From the standpoint of academia, especially theoretical computer science, PCE has been criticized for ignoring finer distinctions in computational complexity, such as P vs NP2. Scott Aaronson and others have argued that it is a leap to treat all systems as “substantially equivalent” simply because they possess universality38.

However, Wolfram’s perspective is directed not toward the efficiency of practical computation, but toward the “qualitative classes of behavior” of systems. The proof of the universality of the (2,3) Turing machine demonstrates that the highest level of computational capability can reside within naturally occurring rules, even without the intention of a designer. In this respect, the foresight of PCE is extremely powerful7.

Conclusion: Universal Intelligence Beyond Simplicity

All the computational systems comprehensively examined in this report show, across formal boundaries, that simple rules generate rich complexity. The sequential complexity shown by mobile automata, the minimal universality shown by Turing machines, and the number-theoretic depth shown by tag systems and register machines all reflect different aspects of the “same truth” within the computational universe.

Complexity is not the product of specific advanced mechanisms, such as parallel processing or large-scale memory, but is built into the root of the operation called computation. And as the Principle of Computational Equivalence claims, most nontrivial systems existing in our universe share equivalent computational sophistication. This fact highlights, in physics, biology, and even artificial intelligence research, the importance of an approach that “searches for” and “makes use of” the “simple and powerful rules” that already exist in the computational universe, rather than attempting to “design” complex phenomena.

Ultimately, the conclusion that complexity is universal suggests that the reason we ourselves are complex beings is also a logical consequence of the simplicity of the universe’s fundamental laws. The computational universe contains infinite stories written with a small number of characters and a few lines of rules.

References

  1. A New Kind of Science \- Wolfram Media, accessed May 15, 2026, https://www.wolfram-media.com/products/nks/
  2. A New Kind of Science \- Wikipedia, accessed May 15, 2026, https://en.wikipedia.org/wiki/A\_New\_Kind\_of\_Science
  3. New Kind of Science \-- from Wolfram MathWorld, accessed May 15, 2026, https://mathworld.wolfram.com/NewKindofScience.html
  4. Mobile Automata: A New Kind of Science | Online by Stephen ..., accessed May 15, 2026, https://www.wolframscience.com/nks/p71--mobile-automata/
  5. Mobile Automaton \-- from Wolfram MathWorld, accessed May 15, 2026, https://mathworld.wolfram.com/MobileAutomaton.html
  6. Mobile Automata, accessed May 15, 2026, https://files.wolframcdn.com/pub/www.wolframscience.com/nks/nks-ch3-sec3.pdf
  7. Wolfram's 2-state 3-symbol Turing machine \- Wikipedia, accessed May 15, 2026, https://en.wikipedia.org/wiki/Wolfram%27s\_2-state\_3-symbol\_Turing\_machine
  8. Universal Turing machine \- Wikipedia, accessed May 15, 2026, https://en.wikipedia.org/wiki/Universal\_Turing\_machine
  9. What's the simplest noncontroversial 2-state universal Turing machine?, accessed May 15, 2026, https://cstheory.stackexchange.com/questions/10207/whats-the-simplest-noncontroversial-2-state-universal-turing-machine
  10. Small universal Turing machines, accessed May 15, 2026, https://www.mobt3ath.com/uplode/book/book-94720.pdf
  11. Small universal Turing machines, accessed May 15, 2026, https://justine.lol/sectorlisp2/tneary\_Thesis.pdf
  12. Substitution Systems and Fractals: A New Kind of Science | Online by Stephen Wolfram \[Page 190\], accessed May 15, 2026, https://www.wolframscience.com/nks/p190--substitution-systems-and-fractals/
  13. Substitution Systems: A New Kind of Science | Online by Stephen Wolfram \[Page 82\], accessed May 15, 2026, https://www.wolframscience.com/nks/p82--substitution-systems/
  14. Substitution Systems and Fractals: A New Kind of Science | Online by Stephen Wolfram \[Page 187\], accessed May 15, 2026, https://www.wolframscience.com/nks/p187--substitution-systems-and-fractals/
  15. Substitution Systems and Fractals: A New Kind of Science | Online by Stephen Wolfram \[Page 191\], accessed May 15, 2026, https://www.wolframscience.com/nks/p191--substitution-systems-and-fractals/
  16. Substitution Systems and Fractals: A New Kind of Science | Online by Stephen Wolfram \[Page 188\], accessed May 15, 2026, https://www.wolframscience.com/nks/p188--substitution-systems-and-fractals/
  17. String Substitution Systems: Wolfram Physics Project Technical Background, accessed May 15, 2026, https://www.wolframphysics.org/technical-introduction/the-updating-process-for-string-substitution-systems/string-substitution-systems/
  18. Sequential Substitution System \-- from Wolfram MathWorld, accessed May 15, 2026, https://mathworld.wolfram.com/SequentialSubstitutionSystem.html
  19. Sequential Substitution Systems: A New Kind of Science | Online by ..., accessed May 15, 2026, https://www.wolframscience.com/nks/p90--sequential-substitution-systems/
  20. Tag System \-- from Wolfram MathWorld, accessed May 15, 2026, https://mathworld.wolfram.com/TagSystem.html
  21. Tag system \- Wikipedia, accessed May 15, 2026, https://en.wikipedia.org/wiki/Tag\_system
  22. \[PDF\] Tag systems and Collatz-like functions \- Semantic Scholar, accessed May 15, 2026, https://www.semanticscholar.org/paper/Tag-systems-and-Collatz-like-functions-Mol/931eeecbcb5a55f31e9aec6c6a628fd348b435c4
  23. On the time complexity of 2-tag systems and small universal Turing machines, accessed May 15, 2026, https://dna.hamilton.ie/assets/dw/WoodsNeary-FOCS06.pdf
  24. \[cs/0612089\] On the time complexity of 2-tag systems and small universal Turing machines, accessed May 15, 2026, https://arxiv.org/abs/cs/0612089
  25. Register machine \- Wikipedia, accessed May 15, 2026, https://en.wikipedia.org/wiki/Register\_machine
  26. Minsky machine \- Esolang, accessed May 15, 2026, https://esolangs.org/wiki/Minsky\_machine
  27. Counter machine \- Wikipedia, accessed May 15, 2026, https://en.wikipedia.org/wiki/Counter\_machine
  28. Computation: Finite and Infinite Machines \- MIT CBA, accessed May 15, 2026, http://www.cba.mit.edu/events/03.11.ASE/docs/Minsky.pdf
  29. FRACTRAN \- Wikipedia, accessed May 15, 2026, https://en.wikipedia.org/wiki/FRACTRAN
  30. Fractran A Simple Programming Language \- HKopp \- koppian adventures, accessed May 15, 2026, https://hkopp.github.io/2018/03/fractran-a-simple-programming-language
  31. Complexity of Fractran and Productivity \- Jörg Endrullis, accessed May 15, 2026, https://joerg.endrullis.de/assets/papers/complexity-productivity-2009.pdf
  32. FRACTRAN: A SIMPLE UNIVERSAL PROGRAMMING LANGUAGE FOR ARITHMETIC \- UNC Computer Science, accessed May 15, 2026, https://www.cs.unc.edu/\~stotts/COMP210-s23/madMath/Conway87.pdf
  33. The Principle of Computational Equivalence, accessed May 15, 2026, https://files.wolframcdn.com/pub/www.wolframscience.com/nks/nks-ch12.pdf
  34. Principle of Computational Equivalence \-- from Wolfram MathWorld, accessed May 15, 2026, https://mathworld.wolfram.com/PrincipleofComputationalEquivalence.html
  35. Computation and the Future of the Human Condition \- Stephen Wolfram, accessed May 15, 2026, https://www.stephenwolfram.com/publications/computation-future-human-condition/
  36. 7.3 Computational Capabilities of Our Models \- The Wolfram Physics Project, accessed May 15, 2026, https://www.wolframphysics.org/technical-introduction/equivalence-and-computation-in-our-models/computational-capabilities-of-our-models/
  37. Computational irreducibility \- Wikipedia, accessed May 15, 2026, https://en.wikipedia.org/wiki/Computational\_irreducibility
  38. Blog Archive » The Aaronson $25.00 Prize \- Shtetl-Optimized, accessed May 15, 2026, https://scottaaronson.blog/?p=284