|
|
|
Viewing Version
1
of
'decides'
|
[ view 'decides'
|
back to history
]
| Title of object: |
decides |
| Canonical Name: |
Decides |
| Type: |
Definition |
| Created on: |
2002-09-05 19:09:43.655573-04 |
| Modified on: |
2002-09-05 19:09:43.655573-04 |
| Classification: |
msc:68Q05, msc:68Q10 |
| Defines: |
enumerates |
Preamble:
Content:
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:
$$x\in L \mathrm{ iff } T \mathrm{ 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$. |
|
|
|
|
|
