decision problem (original) (raw)

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).