Singleton-language problem for Turing machines
= Singleton-language problem for Turing machines
{title2=$\{\langle M\rangle:|L(M)|=1\}$}
It is undecidable whether a <Turing machine> recognizes a <formal language> containing exactly one <word>. Reduce the <halting problem> by a <Turing machine> that rejects every nonempty input and, on the <empty word>, simulates a fixed computation and accepts if that computation halts. Its recognized <formal language> is a <singleton> exactly when the fixed computation halts.