patternMinor
Universal binary rewriting system
Viewed 0 times
universalsystembinaryrewriting
Problem
What is the simplest example of a rewriting system from binary strings to binary strings
$$f:\Sigma^\rightarrow\Sigma^\qquad\Sigma=\{0,1\}$$
that can perform universal computation? Binary string rewriting systems in general can compute any computable function, but I have trouble finding particular instances that can by themselves compute any computable function given an appropriate input. I've seen statements that a class of rewriting systems (e.g., the set of cyclic tag systems) is Turing-complete, but I'm looking for a single rewriting system that is universal.
I was thinking a self-modifying bitwise cyclic tag system might be a candidate, but I'm not sure how to interpret the output of such a system.
$$f:\Sigma^\rightarrow\Sigma^\qquad\Sigma=\{0,1\}$$
that can perform universal computation? Binary string rewriting systems in general can compute any computable function, but I have trouble finding particular instances that can by themselves compute any computable function given an appropriate input. I've seen statements that a class of rewriting systems (e.g., the set of cyclic tag systems) is Turing-complete, but I'm looking for a single rewriting system that is universal.
I was thinking a self-modifying bitwise cyclic tag system might be a candidate, but I'm not sure how to interpret the output of such a system.
Solution
Rule 110 is a binary rewriting system that can perform universal computation, i.e., it has been proven to be universal. It can be implemented by a finite-state transducer: it needs only finite state.
However, Rule 110 is not a tag system or a cyclic tag system, so this does not provide an instance of a specific binary tag system that is known to be universal. It might be that examining the proof of universality of Rule 110 could yield such a system, as apparently the proof involves a reduction that goes by way of cyclic tag systems -- though personally I've never read the proof, so this is only speculation.
A side note: From Rule 110, you can construct a particular queue automaton that is universal: the queue alphabet is $\{0,1,\$\}$ and contains the state of the cellular automaton (a binary string representing the contents of each cell, followed by $\$$). I don't know whether it'd be possible to use this to construct a specific tag system that is universal (e.g., if you can find a way to use a tag system to emulate a queue automaton).
However, Rule 110 is not a tag system or a cyclic tag system, so this does not provide an instance of a specific binary tag system that is known to be universal. It might be that examining the proof of universality of Rule 110 could yield such a system, as apparently the proof involves a reduction that goes by way of cyclic tag systems -- though personally I've never read the proof, so this is only speculation.
A side note: From Rule 110, you can construct a particular queue automaton that is universal: the queue alphabet is $\{0,1,\$\}$ and contains the state of the cellular automaton (a binary string representing the contents of each cell, followed by $\$$). I don't know whether it'd be possible to use this to construct a specific tag system that is universal (e.g., if you can find a way to use a tag system to emulate a queue automaton).
Context
StackExchange Computer Science Q#44213, answer score: 6
Revisions (0)
No revisions yet.