decision problem
Let be a Turing machine and let be a language
. We say decides if for any , accepts , and for any , rejects .
We say enumerates if:
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 to decide , it must be that halts on every input. On the other hand could enumerate if it does not halt on some strings which are not in .
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 accepts is denoted .