Rewrite systems

20260101T235215

A rewrite system models computing using structures and replacement rules over those structures.

Rewrite systems are Turing-complete. See (1), which contains a beautiful diagram in its proof that a Turing machine can be encoded in a single rewrite rule. I could be wrong about that; I haven't read this paper deeply yet.

(1, doi) Simulation of Turing machines by a regular rewrite rule

See (2) on rewrite systems, taken as "nondeterministic Markov algorithms over terms rather than strings."

(2, doi) expository paper

(note) Markov algorithms

In a talk on /democratizing software/, Wryl claims rewrite systems approach "universal [intuitiveness]". In it, Wryl mentions an early version of the Nova programming language.

Wryl's excellent talk

(note) Nova

A multiset rewriting system works by applying replacement rules to an unordered multiset of objects.

hundred rabbits' writing on the subject

Fractran uses the fundamental theorem of arithmetic and the two-part-ness of fractions to encode a multiset rewriting system using only positive rational numbers and multiplication.

100r suggests some connection with reversible computing that I haven't understood but am interested in.

Modal is a rewriting system whose accumulator is an ordered, parenthesized tree of symbols.

Structures

A "loop inhibitor".

Consider a counting loop:

gen -> gen .
gen . . . -> gen action

We can inhibit this loop by leveraging this system's ordered short-circuiting:

gen hold -> gen hold
gen -> gen .
gen . . . -> gen action hold

If there's a `hold`, then the second rule above never matches.

The pattern is flexible. Consider loop modifiers:

gen fast -> gen . .
gen -> .
gen . . . -> gen action