## You are here

Homedecision problem

## Primary tabs

# decision problem

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

## Mathematics Subject Classification

68Q25*no label found*

- Forums
- Planetary Bugs
- HS/Secondary
- University/Tertiary
- Graduate/Advanced
- Industry/Practice
- Research Topics
- LaTeX help
- Math Comptetitions
- Math History
- Math Humor
- PlanetMath Comments
- PlanetMath System Updates and News
- PlanetMath help
- PlanetMath.ORG
- Strategic Communications Development
- The Math Pub
- Testing messages (ignore)

- Other useful stuff
- Corrections