decision problem

Let T be a Turing machineMathworldPlanetmath and let LΓ+ be a languagePlanetmathPlanetmath. We say T decides L if for any xL, T accepts x, and for any xL, T rejects x.

We say T enumeratesMathworldPlanetmath L if:

xL iff T accepts x

For some Turing machines (for instance non-deterministic machines) these definitions are equivalentMathworldPlanetmathPlanetmathPlanetmathPlanetmath, 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).

Title decision problem
Canonical name DecisionProblem
Date of creation 2013-03-22 13:01:33
Last modified on 2013-03-22 13:01:33
Owner Henry (455)
Last modified by Henry (455)
Numerical id 12
Author Henry (455)
Entry type Definition
Classification msc 68Q25
Defines enumerates
Defines decide