When we ask a yes/no question about mathematical objects, the question itself partitions the objects into two sides: the objects for which the answer is yes, and the objects for which the answer is no.

Consider graphs. Now ask:

\[\text{Is the graph } G \text{ connected?}\]

This question divides all graphs into two collections. One collection contains the connected graphs. The other collection contains the graphs that are not connected. Notice that this partition exists before we have written any algorithm to recognize it. It exists just because the question has a yes/no answer for each graph.

A language, in the computability-theory sense used in textbooks, is first a way of naming the yes side of a decision question.

A Turing machine takes a finite string over some alphabet $\Sigma$. So if we want to talk about graphs using Turing machines, we first encode each graph as a string. For a graph $G$, write its encoding as

\[\langle G \rangle \in \Sigma^*.\]

Now the yes side of the question can be written as a set of strings:

\[L = \{\langle G \rangle \in \Sigma^* \mid G \text{ is connected}\}.\]

This set $L$ is the language of connected graphs. It contains exactly the encodings of graphs for which the answer to the question is yes.

The no side is the complement:

\[\overline{L} = \{\langle G \rangle \in \Sigma^* \mid G \text{ is not connected}\}.\]

So $L$ is not the algorithm. It is the target. It tells us which inputs should be accepted if our machine is correctly solving the question. The language describes the yes instances; it does not by itself tell us how to find them.

We need to create a Turing machine $M$ such that, on an input string $x$, it behaves correctly with respect to this language. If the computation eventually reaches the accepting state $q_{\text{accept}}$, then $M$ accepts $x$. If it reaches the rejecting state $q_{\text{reject}}$, then $M$ rejects $x$.

The language of a machine is defined by what it accepts:

\[L(M) = \{x \in \Sigma^* \mid M(x) \text{ eventually reaches } q_{\text{accept}}\}.\]

So $L(M)$ is the set of strings accepted by $M$.

If our question is connectedness of graphs, then we want a machine whose accepted strings are exactly the encodings of connected graphs:

\[L(M) = L.\]

The left side comes from the behavior of the machine. The right side comes from the mathematical question we wanted to answer. Saying $L(M) = L$ means the machine accepts exactly the yes instances of the question.

If $x \in L$, then $M(x)$ eventually reaches $q_{\text{accept}}$. In the graph example, if $x = \langle G \rangle$ and $G$ is connected, then the machine eventually accepts $x$. This makes $M$ a recognizer for $L$: it gives a reliable yes, but $L(M) = L$ does not tell us whether inputs outside $L$ are rejected or whether the machine runs forever.

For a decider, we need both sides. One way to get a decider is to have a recognizer for $L$ and another recognizer for $\overline{L}$. On input $x$, run both recognizers in parallel. If the recognizer for $L$ accepts, accept. If the recognizer for $\overline{L}$ accepts, reject.

Since every encoded object is either in $L$ or in $\overline{L}$, one of the two recognizers must eventually accept. The two one-sided procedures become one two-sided procedure.

Recognition is often easier than decision because it is one-sided. A recognizer only has to verify membership in $L$. In this sense, a recognizer is like a verification procedure for the yes instances. Verifying a yes instance can be easier than solving the whole decision problem.

In symbols, a decider halts on both sides of the partition:

\[x \in L \implies M(x) \text{ reaches } q_{\text{accept}},\]

and

\[x \in \overline{L} \implies M(x) \text{ reaches } q_{\text{reject}}.\]

Now the machine is deciding the question. Given an encoded graph $x$, it eventually gives one of two answers: accept if $x$ is on the yes side, reject if $x$ is on the no side.

This is the role of a language in computability theory. A decision question gives us a partition of objects. Encoding turns those objects into strings. The language $L$ is the set of encoded yes instances. A recognizer accepts exactly those yes instances. A decider accepts the yes instances and rejects the no instances.