We say enumerates if:
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 to decide , it must be that halts on every input. On the other hand could enumerate if it does not halt on some strings which are not in .
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 accepts is denoted .
|Date of creation||2013-03-22 13:01:33|
|Last modified on||2013-03-22 13:01:33|
|Last modified by||Henry (455)|