arXiv preprint ·
Small universal multiset reaction systems
- Published
- Source
- arXiv preprint, posted before peer review
- Original
- Read it at arXiv
- Topics
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.
The authors’ abstract, as arXiv lists it. arXiv’s listings, abstracts included, are free for anyone to reuse.
Read it on ReadSearch
Each opens after you create an account, and brings you back to this paper.
More in Neural & Evolutionary Computing
From Transformers to Weighted Automata: Towards the Verification of Large Language Models
Provably Tractable NFA-Constrained Language Generation via HMMs
Smallest String Attractors and Minimal Coverage Certificates of Thue--Morse Words
Learning Shuffle Ideals with Membership Queries and Contrastive Examples
Type-Checking for Pattern-Based Tree Transformations
Get the few papers worth your time in Neural & Evolutionary Computing every morning.
ReadSearch reads the new papers in your field each day and brings you the few worth reading, each with its key finding in a sentence.