= Solution
An <algorithm> is a finite effective procedure on finitely encoded inputs; a <Turing machine> is one precise model. A decision <algorithm> must halt on every permitted input and answer correctly. An algorithmic problem specifies the input encoding and the required output; enumerating positive answers alone is not a decision <algorithm>.
For a fixed <finite group presentation> $\mathcal P=\langle A\mid R\rangle$, the <word problem for a group> takes a finite word in $A^{\pm1}$ and asks whether it represents the identity. Equality of two represented elements is equivalent to testing $u^{-1}v$. Positive answers are recursively enumerable: enumerate finite products of conjugates of <relators> and their inverses, freely reduce them, and compare with the input. Equivalently enumerate finite labelled <disc diagrams>. The <van Kampen lemma> ensures that every null word eventually appears. For a non-null word this search continues forever. \b[Solvability requires a procedure that also terminates with a negative answer.]
Back to article page
