# 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. – babou Jul 8 '15 at 20:57

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