a problem as a language

This is the single trick that lets one theory talk about every computational problem at once. The idea is to rewrite any yes/no question as the question is this string in this set? You encode each possible input as a string, and you collect together all the inputs whose answer is yes into one set. That set is the language for the problem. Solving the problem then means recognizing the language: deciding, for any input string, whether it belongs.

Concretely, take a yes/no problem and fix a way to write each instance as a string over some alphabet. The language of the problem is the set of all strings that encode a yes instance. For example, the problem is this number prime? becomes the language { binary encodings of primes }; the problem does this graph have a cycle? becomes the language of (encodings of) graphs that have a cycle. A machine solves the problem exactly when, given the encoded string, it accepts the yes-instances and rejects the no-instances. The encoding details (how you turn a graph or a number into symbols) are assumed to be reasonable and are usually glossed over because they do not change what is solvable.

Why insist on this reformulation? Because it unifies wildly different problems into one uniform shape, so that a single notion of machine, a single notion of accepting, and a single hierarchy of difficulty can cover them all. Two honest caveats. First, this framing naturally fits decision (yes/no) problems; problems that ask to produce an output (like sort this list) need a related but slightly different setup using transducers. Second, the encoding must be sensible: a deliberately wasteful encoding can distort complexity measurements, which is why the theory assumes a reasonable encoding.