Let L be a language, i.e. a subset of Σ∗. Saying that a Turing machine decides the language L means the following. For any word w, if the machine starts with just w on the tape and the head on the leftmost character (or just on a blank if w = ε), the machine eventually returns True if w ∈ L, and False if w \∈L. For a given language L, we can ask: is there a polytime TM that decides it? A language thus corresponds to a decision problem, i.e. a problem where the answer is True or False