decision problem

Let $T$ be a Turing machine and let $L\subseteq {\mathrm{\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)$.

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