User:CircuitCraft/Definition:Thue Machine

Definition

Let $\Sigma$ be a finite set.

Let $\Sigma^*$ be the set of finite strings from $\Sigma$.

Let $\vdash \subset \Sigma^* \times \Sigma^*$ be a symmetric relation.

Let $M$ be the semi-Thue machine over $\Sigma$ generated by $\vdash$.

Then $M$ is the Thue machine over $\Sigma$ generated by $\vdash$.