Multiset reaction systems simulate universal computers with few parts
Small universal multiset reaction systems
Neural and Evolutionary ComputingFormal Languages and Automata Theory
Summary
This paper shows that a simplified kind of chemical-like system called a multiset reaction system can perform any computer calculation. The authors built a tiny universal machine inside this framework by encoding computer steps as special elements that trigger reactions in order. Their example uses just 87 different elements to simulate a machine with 8 memory slots and 23 instructions. This proves that these reaction systems can do everything a normal computer can, using surprisingly few components.
What this means in practice
- •For chemical computing developers: Design minimal reaction networks for computing tasks by encoding instructions and states as reacting elements.
- •For programming language designers: Inform development of new languages based on chemical or reaction-based computation models through small universal systems.
Authors
Andrei Paun, Annemarie-Beatrix Messner
Abstract
This paper presents a construction of a small universal machine within the framework of Multi-set Reaction Systems. We encode the machine state using elements that represent registers and instruction labels, and we enforce sequential execution by ensuring that reaction chains for a given instruction can only activate after the corresponding label element appears. We implement a universal register machine with 8 registers and 23 instructions, showing that the priority-based model requires 87 distinct elements. The results demonstrate that multiset reaction systems are capable of simulating universal computation.