# Universal binary rewriting system

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.

• I understood your question as being about string rewriting systems, such as Chomsky type 0 grammars (Semi-Thue grammars). But none of the solutions being considered seems to fit. What did you precisely mean by "rewriting system from binary strings to binary strings"? For Chomsky type 0 grammars, I do not see how it can be achieved, unless the input is first encoded with another device. Jul 8 '15 at 20:57

## 2 Answers

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).

• Thank you. Is there an example of a system that manipulates only a finite amount of memory at any given time, e.g. a binary tag system? My understanding is that a non-standard initial state was required to show the rule 110 cellular automaton was universal. Jul 7 '15 at 19:43

Binary Combinatory Logic is an example with simple rewriting rules.

• Of course! Even simpler, perhaps, would be one based on a single combinator? cstheory.stackexchange.com/questions/31883/… Jul 23 '15 at 2:49
• Any single-combinator formulation will almost certainly have much more complicated operational rewriting rules. (The "smallness" of languages such as Iota and Jot, for example, is only wrt the denotational semantics -- their operational semantics are more complicated than BCL.) Jul 23 '15 at 12:35