Question:
Which of the following problems is known to be undecidable?
निम्नलिखित में से कौन सी समस्या अनिर्धार्य (Undecidable) मानी जाती है?
Options:
- The Halting Problem for Turing Machines
- Emptiness problem for Context-Free Languages
- Membership problem for Regular Languages
- Equivalence problem for Deterministic Finite Automata (DFA)
- ट्यूरिंग मशीनों के लिए हाल्टिंग समस्या (Halting Problem)
- संदर्भ-मुक्त भाषाओं (CFL) के लिए शून्यता समस्या
- नियमित भाषाओं के लिए सदस्यता समस्या
- DFA के लिए तुल्यता समस्या
Correct Answer: a)
Explanation:
Alan Turing proved in 1936 that the Halting Problem (determining whether an arbitrary Turing machine halts on a given input) is undecidable. Membership in regular languages, equivalence of DFAs, and CFG emptiness are all decidable.
एलन ट्यूरिंग ने सिद्ध किया था कि ट्यूरिंग मशीन की हाल्टिंग समस्या अनिर्धार्य (Undecidable) है। जबकि DFA और रेगुलर भाषाओं की समस्याएं निर्धार्य हैं।