6
$\begingroup$

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.

Improve this question
$\endgroup$
1
  • $\begingroup$ 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. $\endgroup$
    – babou
    Commented Jul 8, 2015 at 20:57

2 Answers 2

Reset to default
6
$\begingroup$

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

Improve this answer
$\endgroup$
1
  • $\begingroup$ 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. $\endgroup$
    – user76284
    Commented Jul 7, 2015 at 19:43
3
$\begingroup$

Binary Combinatory Logic is an example with simple rewriting rules.

Improve this answer
$\endgroup$
2
  • $\begingroup$ Of course! Even simpler, perhaps, would be one based on a single combinator? cstheory.stackexchange.com/questions/31883/… $\endgroup$
    – user76284
    Commented Jul 23, 2015 at 2:49
  • 1
    $\begingroup$ 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.) $\endgroup$
    – r.e.s.
    Commented Jul 23, 2015 at 12:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.