What is the difference between an algorithm, a language and a problem?

For simplicity, I’ll begin by only considering “decision” problems, which have a yes/no answer. Function problems work roughly the same way, except instead of yes/no, there is a specific output word associated with each input word. Language: a language is simply a set of strings. If you have an alphabet, such as $Sigma$, then $Sigma^*$ is the set of all words containing only the symbols in $Sigma$. For example, ${0,1 }^*$ is the set of all binary sequences of any length. An alphabet doesn’t need to be binary, though. It can be unary, ternary, etc. A language over an alphabet $Sigma$ is any subset of $Sigma^*$. Problem: A problem is some question about some input we’d like answered. Specifically, a decision problem is a question which asks, “Does our given input fulfill property $X$? A language is the formal realization of a problem. When we want to reason theoretically about a decision problem, we often examine the corresponding language. For a problem $X$, the corresponding language is:

$L = {w mid w$ is the encoding of an input $y$ to problem $X$, and the answer to input $y$ for problem $X$ is “Yes” $ }$

Determining if the answer for an input to a decision problem is “yes” is equivalent to determining whether an encoding of that input over an alphabet is in the corresponding language. Algorithm: An algorithm is a step-by-step way to solve a problem. Note that there an algorithm can be expressed in many ways and many languages, and that there are many different algorithms solving any given problem. Turing Machine: A Turing Machine is the formal analogue of an algorithm. A Turing Machine over a given alphabet, for each word, either will or won’t halt in an accepting state. Thus for each Turing Machine $M$, there is a corresponding language:

$L(M) = {w mid M$ halts in an accepting state on input $w}$.

(There’s a subtle difference between Turing Machines that halt on all inputs and halt on yes inputs, which defines the difference between complexity classes $mathsf{R}$ and $mathsf{RE}$.) The relationship between languages and Turing Machines is as follows

1. Every Turing Machine accepts exactly one language
2. There may be more than one Turing Machine that accept a given language
3. There may be no Turing Machine that accepts a given language.

We can say roughly the same thing about algorithms and problems: every algorithm solves a single problem, but there may be 0, or many, algorithms solving a given problem. Time Complexity: One of the most common sources of confusion between algorithms and problems is in regards to complexity classes. The correct allocation can be summarized as follows:

• An algorithm has a time complexity
• A problem belongs to a complexity class

An algorithm can have a certain time complexity. We say an algorithm has a worst-case upper-bounded complexity $f(n)$ if the algorithm halts in at most $f(n)$ steps for any input of size $n$. Problems don’t have run-times, since a problem isn’t tied to a specific algorithm which actually runs. Instead, we say that a problem belongs to a complexity class, if there exists some algorithm solving that problem with a given time complexity. $mathsf{P}, mathsf{NP}, mathsf{PSPACE}, mathsf{EXPTIME}$ etc. are all complexity classes. This means they contain problems, not algorithms. An algorithm can never be in $mathsf{P}$, but if there’s a polynomial-time algorithm solving a given problem $X$, then $X$ is in $mathsf{P}$. There could also be a bunch of exponential-time algorithms accepting $X$, but since there exists a single polynomial-time algorithm accepting $X$, it is in $mathsf{P}$.