# 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 |