Turing Recognizable, Turing Decidable and Turing Enumerable

A Turing Machine can end up in one of three possibilities

Accept and halt by ending up in $q_{accept}$ .
Reject and halt by ending up in $q_{reject}$ .
Run forever.

Turing Recognizable

The language recognized by a Turing Machine is the set of strings that the machine accepts.

A language is Turing recognizable if it is recognized by some Turing Machine. Thus, if a string belongs to a a language that is Turing recognizable, there exists some Turing Machine which will accept that string. However, strings that do not belong to the language may run forever.

Turing Decidable

A Turing Machine is a decider if it halts on every input.

A language is Turing decidable if it is recognized by a Turing Machine decider. Thus, in addition to the Turing Machine accepting all strings that belong to the language, it should reject all strings that do not belong to the language. The machine halts on every input.

It is easy to see that every Turing Decidable language is Turing Recognizable.

Turing Enumerable

A Turing Machine (with an additional output tape) is an enumerator for a language if when started on an empty input, it writes all strings that belong to the language on the output tape. For the sake of clarity, each string is separated by a distinct symbol.

A TM enumerator ensures two things

Only strings that belong to the language appear on the output tape
If a string belongs to the language, it will be written on the ouput tape after some finite amount of time.

While enumerating, the strings can appear multiple times or/and out-of-order.

A language is Turing enumerable if some Turing Machine enumerates it.

Enumerable implies Recognizable

Say the language $L$ is Turing Enumerable. Let the machine $E$ be the enumerator for it.

To recognize $L$

On input $w$ , run $E$
When $E$ outputs a string, say $x$ , check whether $w == x$ .
If yes, accept.

If $w \in L$ , after a finite amount of time it will be accepted. If $w \notin L$ , the machine may run forever.

Recognizable implies Enumerable

Say the language $L$ is Turing Recognizable. Let the machine $R$ be the recognizer for it.

To enumerate $L$

On empty input
$i = 0$
Repeat
1. $i = i+1$
2. Generate first $i$ strings (in some order) from $\Sigma^*$ . Let these be $w_1 \cdots w_i$ .
3. For each
  1. Run $R$ on $w_j$ for at max $i$ transitions
  2. If $R$ accepts $w_j$ , print $w_j$ on the output tape

Each string $w$ is limited to $i$ number of transitions on $R$ . This ensures that the above algorithm never gets stuck. $i$ is incremented in each iteration. This gives the option to rerun $R$ on the same string for greater number of transitions.

Say $R$ accepts $w$ in $s$ transitions. Let $w$ be the $t^\text{th}$ string in order in $\Sigma^*$ . Then, the enumerator is guaranteed to output the string in $max(t,s)$ iterations.

Every string that is accepted gets printed on the output tape infinite number of times.

The Beard Sage