| Version 3 |
Version 2 |
| 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 \mathrm{ iff } T \mathrm{ accepts } x$$
|
| The language enumerated by $T$ is denoted $L(T)$. |
The language enumerated by $T$ is denoted $L(T)$. |
| 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$. |
