| Version current |
Version 8 |
| Let $T$ be a Turing machine and let $L\subseteq\Gamma^+$ be a language. We say $T$ \emph{decides} $L$ if for any $x\in L$, $T$ accepts $x$, and for any $x\notin L$, $T$ rejects $x$. |
Let $T$ be a Turing machine and let $L\subseteq\Gamma^+$ be a language. We say $T$ \emph{decides} $L$ if for any $x\in L$, $T$ accepts $x$, and for any $x\notin L$, $T$ rejects $x$. |
|
|
| We say $T$ \emph{enumerates} $L$ if: |
We say $T$ \emph{enumerates} $L$ if: |
| $$x\in L \text{ iff } T \text{ accepts } x$$ |
$$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$. |
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 \emph{decision problem}, and a Turing machine which decides it is said to solve the decision problem. |
$L$ is sometimes said to be a \emph{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)$. |
The set of strings which $T$ accepts is denoted $L(T)$. |
