# Turing Recognizable, Turing Decidable and Turing Enumerable

A Turing Machine can end up in one of three possibilities

1. Accept and halt by ending up in .
2. Reject and halt by ending up in .
3. 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

1. Only strings that belong to the language appear on the output tape
2. 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 is Turing Enumerable. Let the machine be the enumerator for it.

To recognize

1. On input , run
2. When outputs a string, say , check whether .
3. If yes, accept.

If , after a finite amount of time it will be accepted. If , the machine may run forever.

## Recognizable implies Enumerable

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

To enumerate

1. On empty input
2. Repeat
1. Generate first strings (in some order) from . Let these be .
2. For each
1. Run on for at max transitions
2. If accepts , print on the output tape

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

Say accepts in transitions. Let be the string in order in . Then, the enumerator is guaranteed to output the string in iterations.

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