rewriting systems have the full power of Turing machines, that is, every computable function can be defined by a term rewriting system.

Some programming languages are based on term rewriting. One such example is Pure, a functional programming language for mathematical applications.

Formal definition

A rewrite rule is a pair of terms, commonly written as