In this tutorial, we’ll study recognizable, co-recognizable, and decidable languages.
Such problems have a direct correspondence to languages. A language represents a problem if and only if we can map any instance of to a word and vice versa. This allows us to study those problems using the results of the theory of formal languages and Turing machines.
However, we don’t solve those problems using Turing machines. Instead, we formulate algorithms and use higher-level programming languages to implement them. This isn’t an issue for computer science theory since we can convert those algorithms to Turing machines.
2. Turing Machines and Languages
First, let’s revise how a Turing machine (TM) works.
A TM accepts a word if it ends in an accepting state after reading the entire word. The language a machine recognizes consists of all the words it accepts – . Analogously, a TM rejects a word if it finishes in a non-accepting state after reading it.
However, a TM can end in a loop for some input words. In that case, we say it neither accepts nor rejects the input.
3. Language Categorization
For each language , we can ask if a Turing machine accepts all the words from . We can ask about its complement .
Based on the answers, we categorize languages into three types:
3.1. Recognizable Languages
A language is recognizable if there’s a Turing machine that accepts all the words . Nothing is implied about the complement of . The machine can reject a word from or run forever in a loop.
For example, let .
For any string , a recognizer of should switch between its states based on the counts of , , and in . If it finds at least one , an odd number of s, and an even number of s, it will accept an input word. So, is recognizable.
3.2. Co-recognizable Languages
A language is co-recognizable if its complement is recognizable.
Therefore, a Turing machine must exist for . That means an algorithm (a TM) can accept a word that isn’t in the language but rejects or run forever if the input is in .
For instance, the language of Turing machines that don’t halt on empty input is co-recognizable. Here, our input is a string representation of a TM. We run it on the universal Turing machine, and if it halts, we identify a machine from the complement language. Since we can’t end the simulation to return a yes if the machine halts when we feed it an empty input, we can’t recognize the target language.
So, a language can be co-recognizable but not recognizable, and vice versa. It can also be neither. However, some languages are both.
3.3. Decidable Languages
A language is decidable if it’s recognizable and co-recognizable:
A decider is a TM that always halts. We can construct a decider for by combining and :
It forwards the input to both and . Now, by construction, if , then will accept it and won’t. The converse holds for . So, we define the decider’s output based on which constituent machine accepts or rejects the input word. Since is recognizable and co-recognizable, one of them is guaranteed to accept it.
So, a decider always halts, but a recognizer can end in a loop if the input word belongs to the complement of the language it recognizes.
In this article, we’ve gone through language categorization based on the Turing machine. A language is decidable if it’s both recognizable and co-recognizable.