Let $T$ be a Turing machine and let $L\subseteq\Gamma^+$ be a language. We say $T$ decides $L$ if for any $x\in L$ , $T$ accepts $x$ , and for any $x\notin L$ , $T$ rejects $x$ .

We say $T$ enumerates $L$ if: $$x\in L \text{ iff } T \text{ accepts } x$$

For some Turing machines (for instance non-deterministic machines) these definitions are equivalent, but for others they are not. For example, in order for a deterministic Turing machine $T$ to decide $L$ , it must be that $T$ halts on every input. On the other hand $T$ could enumerate $L$ if it does not halt on some strings which are not in $L$ .

$L$ is sometimes said to be a decision problem, and a Turing machine which decides it is said to solve the decision problem.

The set of strings which $T$ accepts is denoted $L(T)$ .