2 votes 2 votes Theory of Computation theory-of-computation turing-machine + – KISHALAY DAS asked Dec 14, 2016 KISHALAY DAS 615 views answer comment Share Follow See 1 comment See all 1 1 comment reply Gate Mission 1 commented Dec 14, 2016 reply Follow Share option d ? 1 votes 1 votes Please log in or register to add a comment.
0 votes 0 votes Option D I think so.. Surajit answered Dec 16, 2016 Surajit comment Share Follow See all 4 Comments See all 4 4 Comments reply KISHALAY DAS commented Dec 16, 2016 reply Follow Share Yes it is given D..please explain 0 votes 0 votes Akriti sood commented Dec 17, 2016 reply Follow Share please explain the answer. 0 votes 0 votes Surajit commented Dec 17, 2016 reply Follow Share 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. 2 votes 2 votes Akriti sood commented Dec 17, 2016 reply Follow Share thanks suraj..:-) 0 votes 0 votes Please log in or register to add a comment.