Languages recognized and decided by a Turing machine

Let $M$ be a deterministic one-tape Turing machine with input alphabet $\mathrm{\Sigma }$, and let $L\subseteq {\mathrm{\Sigma }}^{\ast }$ be a language (Languages over an alphabet).

We say that $M$ recognizes $L$ if for every input word $w\in {\mathrm{\Sigma }}^{\ast }$, $w\in L⟺M\text{ has an accepting computation on }w\mathrm{.}$

We say that $M$ decides $L$ if $M$ recognizes $L$ and halts on every input $w\in {\mathrm{\Sigma }}^{\ast }$.

Equivalently, $M$ decides $L$ exactly when every input has either an accepting or rejecting computation history and $w\in L⟺M\text{ accepts }w,w\mathrm{\notin }L⟺M\text{ rejects }w\mathrm{.}$

• A recognizer may diverge on words not in the language. Total halting is the extra condition that upgrades recognition to decision.

• The ambient alphabet $\mathrm{\Sigma }$ matters: recognition and decidability are always statements about a subset of one fixed ${\mathrm{\Sigma }}^{\ast }$.