Semigroup presentation ($⟨X\mid u_i=v_i⟩$)

A semigroup presentation specifies generators $X$ and equalities between nonempty words. The resulting semigroup is the quotient of the free semigroup $X^{+}$ by the smallest congruence containing these equalities. Two words are equal precisely when one can be transformed into the other by finitely many replacements in contexts, using the defining equalities in either direction.

A semigroup presentation is finite when both its generator set and its list of defining equalities are finite. A finite transition table for a Turing machine can be encoded this way: state-and-tape words simulate transitions, boundary rules supply blank cells, and halting-state rules erase the configuration to one distinguished symbol.

A finite deterministic Turing machine can be represented by a finite semigroup presentation whose generators are tape symbols, state symbols, a boundary marker $h$, and an accept symbol $q$. Defining equalities replace the local scanned symbol and state according to machine instructions, with separate boundary cases for implicit blanks. Only terminal-state equalities erase tape letters and then replace $h{q}_{H}h$ by $q$. A derivation from an initial description to $q$ must encounter a terminal state before its first erasure. Simulation equalities preserve halting membership in either direction: for a deterministic transition $C\to D$, $C$ halts if and only if $D$ halts. Thus reverse use of defining equalities cannot create a false halting certificate. Boundary and erasure rules require explicit checking for every chosen encoding.