Singleton-language problem for Turing machines

ID: singleton-language-problem-for-turing-machines

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.

New to topics? Read the docs here!