Question

The language \( L = \{M | M \text{ halts on all inputs}\} \) is _______ .

• A. Decidable
• B. Undecidable but recognizable
• C. Not recognizable
• D. Regular

Hint:

The Halting Problem is undecidable, but certain properties, like whether a machine halts on all inputs, can be recognized in some cases.

Answer 1

The Correct Option is B

The language \( L = \{M | M \text{ halts on all inputs}\} \) is undecidable, as it corresponds to the Halting Problem, which is famously undecidable. However, it is recognizable because we can verify if a machine halts on all inputs by running it and checking whether it halts. If the machine halts on all inputs, we can recognize it, but we cannot decide it in general.