GATE Exam > GATE Questions > Which of the following languages are undecida...
Start Learning for Free
Which of the following languages are undecidable? Note that 〈 M〉 indicates encoding of the Turing machine M.
L1 = {〈M〉⏐L(M) = φ]
L2 = {〈M, w, q〉⏐M on input w reaches state q in exactly 100 steps}
L3 = {〈M〉⏐L(M) is not recursive)
L4 = {〈M〉⏐L(M) contains at least 21 members)
L1 = {〈M〉⏐L(M) = φ]
L2 = {〈M, w, q〉⏐M on input w reaches state q in exactly 100 steps}
L3 = {〈M〉⏐L(M) is not recursive)
L4 = {〈M〉⏐L(M) contains at least 21 members)
- a)L2, L3 and L4 only
- b)L1, L3 and L4 only
- c)L1 and L3 only
- d)L2 and L3 only
Correct answer is option 'B'. Can you explain this answer?
| FREE This question is part of | Download PDF Attempt this Test |
Verified Answer
Which of the following languages are undecidable? Note that M indicat...
Rice’s theorem applies to L1, L3 and L4 since then have condition based on L(M), which are non-trivial.
L1 : L(M)= φ is non-trivial condition because some Turing machines accept φ and some don’t.
L3 : L(M)= non-recursive, is non-trivial because some Turing machines accept nonrecursive and some accept recursive.
L4 : ⏐L(M)⏐ ≥ 21 is non-trivial since some Turing machines accept more than 21 strings, some accept less.
L2 : We cannot apply Rice’s theorem since condition is not on L(M) but on M reaching a state q in exactly 100 steps which can be checked on a UTM.
So L2 is decidable.
So, option (b), L1, L3 and L4 are undecidable is correct.
L1 : L(M)= φ is non-trivial condition because some Turing machines accept φ and some don’t.
L3 : L(M)= non-recursive, is non-trivial because some Turing machines accept nonrecursive and some accept recursive.
L4 : ⏐L(M)⏐ ≥ 21 is non-trivial since some Turing machines accept more than 21 strings, some accept less.
L2 : We cannot apply Rice’s theorem since condition is not on L(M) but on M reaching a state q in exactly 100 steps which can be checked on a UTM.
So L2 is decidable.
So, option (b), L1, L3 and L4 are undecidable is correct.
Most Upvoted Answer
Which of the following languages are undecidable? Note that M indicat...
Explanation:
L1 = {ML(M) = φ}
- L1 is decidable as it checks if the language accepted by Turing machine M is empty or not, which is a decidable problem.
L2 = {M, w, qM on input w reaches state q in exactly 100 steps}
- L2 is undecidable as it involves checking the exact number of steps a Turing machine takes to reach a specific state on a specific input, which is a non-trivial property.
L3 = {ML(M) is not recursive}
- L3 is undecidable as it involves determining if the language accepted by Turing machine M is not a recursive language, which is a non-trivial property.
L4 = {ML(M) contains at least 21 members}
- L4 is undecidable as it involves counting the number of members in the language accepted by Turing machine M, which is a non-trivial property.
Therefore, the languages L2, L3, and L4 are undecidable. Hence, the correct answer is option 'B' - L1, L3, and L4 only.
|
Explore Courses for GATE exam
|
|
Which of the following languages are undecidable? Note that M indicates encoding of the Turing machine M.L1 = {ML(M) = φ]L2 = {M, w, qM on input w reaches state q in exactly 100 steps}L3 = {ML(M) is not recursive)L4 = {ML(M) contains at least 21 members)a)L2, L3 and L4 onlyb)L1, L3 and L4 onlyc)L1 and L3 onlyd)L2 and L3 onlyCorrect answer is option 'B'. Can you explain this answer?
Question Description
Which of the following languages are undecidable? Note that M indicates encoding of the Turing machine M.L1 = {ML(M) = φ]L2 = {M, w, qM on input w reaches state q in exactly 100 steps}L3 = {ML(M) is not recursive)L4 = {ML(M) contains at least 21 members)a)L2, L3 and L4 onlyb)L1, L3 and L4 onlyc)L1 and L3 onlyd)L2 and L3 onlyCorrect answer is option 'B'. Can you explain this answer? for GATE 2024 is part of GATE preparation. The Question and answers have been prepared according to the GATE exam syllabus. Information about Which of the following languages are undecidable? Note that M indicates encoding of the Turing machine M.L1 = {ML(M) = φ]L2 = {M, w, qM on input w reaches state q in exactly 100 steps}L3 = {ML(M) is not recursive)L4 = {ML(M) contains at least 21 members)a)L2, L3 and L4 onlyb)L1, L3 and L4 onlyc)L1 and L3 onlyd)L2 and L3 onlyCorrect answer is option 'B'. Can you explain this answer? covers all topics & solutions for GATE 2024 Exam. Find important definitions, questions, meanings, examples, exercises and tests below for Which of the following languages are undecidable? Note that M indicates encoding of the Turing machine M.L1 = {ML(M) = φ]L2 = {M, w, qM on input w reaches state q in exactly 100 steps}L3 = {ML(M) is not recursive)L4 = {ML(M) contains at least 21 members)a)L2, L3 and L4 onlyb)L1, L3 and L4 onlyc)L1 and L3 onlyd)L2 and L3 onlyCorrect answer is option 'B'. Can you explain this answer?.
Which of the following languages are undecidable? Note that M indicates encoding of the Turing machine M.L1 = {ML(M) = φ]L2 = {M, w, qM on input w reaches state q in exactly 100 steps}L3 = {ML(M) is not recursive)L4 = {ML(M) contains at least 21 members)a)L2, L3 and L4 onlyb)L1, L3 and L4 onlyc)L1 and L3 onlyd)L2 and L3 onlyCorrect answer is option 'B'. Can you explain this answer? for GATE 2024 is part of GATE preparation. The Question and answers have been prepared according to the GATE exam syllabus. Information about Which of the following languages are undecidable? Note that M indicates encoding of the Turing machine M.L1 = {ML(M) = φ]L2 = {M, w, qM on input w reaches state q in exactly 100 steps}L3 = {ML(M) is not recursive)L4 = {ML(M) contains at least 21 members)a)L2, L3 and L4 onlyb)L1, L3 and L4 onlyc)L1 and L3 onlyd)L2 and L3 onlyCorrect answer is option 'B'. Can you explain this answer? covers all topics & solutions for GATE 2024 Exam. Find important definitions, questions, meanings, examples, exercises and tests below for Which of the following languages are undecidable? Note that M indicates encoding of the Turing machine M.L1 = {ML(M) = φ]L2 = {M, w, qM on input w reaches state q in exactly 100 steps}L3 = {ML(M) is not recursive)L4 = {ML(M) contains at least 21 members)a)L2, L3 and L4 onlyb)L1, L3 and L4 onlyc)L1 and L3 onlyd)L2 and L3 onlyCorrect answer is option 'B'. Can you explain this answer?.
Solutions for Which of the following languages are undecidable? Note that M indicates encoding of the Turing machine M.L1 = {ML(M) = φ]L2 = {M, w, qM on input w reaches state q in exactly 100 steps}L3 = {ML(M) is not recursive)L4 = {ML(M) contains at least 21 members)a)L2, L3 and L4 onlyb)L1, L3 and L4 onlyc)L1 and L3 onlyd)L2 and L3 onlyCorrect answer is option 'B'. Can you explain this answer? in English & in Hindi are available as part of our courses for GATE.
Download more important topics, notes, lectures and mock test series for GATE Exam by signing up for free.
Here you can find the meaning of Which of the following languages are undecidable? Note that M indicates encoding of the Turing machine M.L1 = {ML(M) = φ]L2 = {M, w, qM on input w reaches state q in exactly 100 steps}L3 = {ML(M) is not recursive)L4 = {ML(M) contains at least 21 members)a)L2, L3 and L4 onlyb)L1, L3 and L4 onlyc)L1 and L3 onlyd)L2 and L3 onlyCorrect answer is option 'B'. Can you explain this answer? defined & explained in the simplest way possible. Besides giving the explanation of
Which of the following languages are undecidable? Note that M indicates encoding of the Turing machine M.L1 = {ML(M) = φ]L2 = {M, w, qM on input w reaches state q in exactly 100 steps}L3 = {ML(M) is not recursive)L4 = {ML(M) contains at least 21 members)a)L2, L3 and L4 onlyb)L1, L3 and L4 onlyc)L1 and L3 onlyd)L2 and L3 onlyCorrect answer is option 'B'. Can you explain this answer?, a detailed solution for Which of the following languages are undecidable? Note that M indicates encoding of the Turing machine M.L1 = {ML(M) = φ]L2 = {M, w, qM on input w reaches state q in exactly 100 steps}L3 = {ML(M) is not recursive)L4 = {ML(M) contains at least 21 members)a)L2, L3 and L4 onlyb)L1, L3 and L4 onlyc)L1 and L3 onlyd)L2 and L3 onlyCorrect answer is option 'B'. Can you explain this answer? has been provided alongside types of Which of the following languages are undecidable? Note that M indicates encoding of the Turing machine M.L1 = {ML(M) = φ]L2 = {M, w, qM on input w reaches state q in exactly 100 steps}L3 = {ML(M) is not recursive)L4 = {ML(M) contains at least 21 members)a)L2, L3 and L4 onlyb)L1, L3 and L4 onlyc)L1 and L3 onlyd)L2 and L3 onlyCorrect answer is option 'B'. Can you explain this answer? theory, EduRev gives you an
ample number of questions to practice Which of the following languages are undecidable? Note that M indicates encoding of the Turing machine M.L1 = {ML(M) = φ]L2 = {M, w, qM on input w reaches state q in exactly 100 steps}L3 = {ML(M) is not recursive)L4 = {ML(M) contains at least 21 members)a)L2, L3 and L4 onlyb)L1, L3 and L4 onlyc)L1 and L3 onlyd)L2 and L3 onlyCorrect answer is option 'B'. Can you explain this answer? tests, examples and also practice GATE tests.
|
|
Explore Courses for GATE exam
|
|
Signup for Free!
Signup to see your scores go up within 7 days! Learn & Practice with 1000+ FREE Notes, Videos & Tests.
|
© EduRev
|
Education Revolution
|
Follow Us
|
Signup to see your scores
go up within 7 days!
Access 1000+ FREE Docs, Videos and Tests
Takes less than 10 seconds to signup