ACE-MockTest2:Turing Machine Decidability Problem

Question

Comments

option d ?

Answer 1

Option D I think so..

Comments

Yes it is given D..please explain

---

please explain the answer.

---

If you see option A and option B are just complements of each other.Both A and B are undeciable since we cannot build a TM to simulate all other TMs to check if it accepts empty language or not.If it was we can use this as a sub-program using reducibaility to solve the halting problem which we know is undeciable.Also A is a R.E however, we can verify if there is atleast one string which is accepted by TM, but the complement of R.E language is not R.E so B is not R.E even.Option C says simply asks if a TM accepts itself as an input or not,i.e can it find whether it is accepting or rejecting a string or not.This is also undeciable and one can use reducibality to halting problem. Option D already mentions we know which are the TMs which accepts their strings(i.e valid strings). Hence option D is right I believe. Please read first few pages in 'Undecidabilty' chapter in Ullman book because proofs are given in detailed there and better explaination is given and I think same examples are there as well.

---

thanks suraj..:-)