= Solution
\b[The problem is undecidable.] Reduce the <halting problem> to it. Given a <Turing machine> $M$ and input <word> $w$, construct a <Turing machine> $T$ over $\{a,b,c\}$ with the following behavior on input $x$:
* If $x\ne\varepsilon$, reject.
* If $x=\varepsilon$, simulate $M$ on the fixed <word> $w$. If that simulation ever halts, whether accepting or rejecting, accept $x$; otherwise continue the simulation forever.
This is an effective construction: $M,w$ are fixed data stored in the description of $T$. Its recognized <formal language> is
$$
\boxed{L(T)=\begin{cases}\{\varepsilon\}&M\text{ halts on }w,\\\varnothing&M\text{ does not halt on }w.\end{cases}}
$$
Therefore $T$ accepts exactly one input <word> if and only if $M$ halts on $w$. A supposed decision procedure for the <singleton-language problem for Turing machines>, applied to the constructed $T$, would decide the <halting problem>. The standard undecidability of the <halting problem> excludes that possibility.
$$
\boxed{\text{The singleton-language problem for Turing machines is undecidable}.}
$$
Back to article page
