2 votes 2 votes Which of the following is/are NOT turing-recognizable? 1. L1={M1M2|M1M2 are Turing Machines with L(M1)=L(M2)} 2. L2={M,w|M is a Turing Machine that halts on input w} 3. L3={M,w|M is a Turing Machine that accepts string w} 4.All of the Above Theory of Computation theory-of-computation turing-machine recursive-and-recursively-enumerable-languages + – Archies09 asked Jan 2, 2017 • retagged Jul 4, 2017 by Arjun Archies09 667 views answer comment Share Follow See all 3 Comments See all 3 3 Comments reply santhoshdevulapally commented Jan 2, 2017 reply Follow Share i)Equivalence property of REL's are undecidable.so it is non REL ii)halting problem also undecidable,we cannot guarantee a particular string hlats on TM so it is non REL. iii)membership property also undecidable,so it is non REL. i think all are not REL's. 0 votes 0 votes focus _GATE commented Jan 2, 2017 reply Follow Share 1. will be RE BUT NOT REC 2.halting problem is also RE BUT NOT REC 3.membership problem of tm is also RE BUT NOT REC. 4) option should be ans . @Arjun sir ?? 0 votes 0 votes Archies09 commented Jan 2, 2017 reply Follow Share Option given in the solution was A. Options B and C were given Turing recognizable languages. 0 votes 0 votes Please log in or register to add a comment.