These slides will be explaining decidability and Rice’s theorem. You can ask if anything is not clear. Part 2 is added now... Decidability Slides Updated Theory of Computation decidability slides + – Prev post >> AAI JE IT results out! Adv no 02/2018 Next post >> PSU's Arjun posted Jan 16, 2019 edited Jan 27, 2019 by Arjun Arjun 5,149 views 59Like17Love1Haha0Wow0Angry0Sad comment 33 Comments See all 33 Comments See all 33 33 Comments reply Shaik Masthan commented Jan 16, 2019 Like 28321 reply Follow Share Gotham City suffers from something, then BATMAN rises ! If GO people suffers from something, then ARJUN SURESH sir rises ! Shamim Ahmed commented Jan 17, 2019 Like reply Follow Share Thank you sir! Utkarsh Joshi commented Jan 17, 2019 Like reply Follow Share Thanks :) suniljha commented Jan 17, 2019 Like reply Follow Share @arjun sir along with this are there any other resources regarding decidability? MiNiPanda commented Jan 17, 2019 Like reply Follow Share @Arjun Sir, @Subarna Das & @Sukanya Das Thanks for all your efforts. It was helpful :) Just a correction (though very minor) Slide 11 (Property of set) : Is 1/x an element of N?- satisfied by NO x But its satisfied only when x=1 abdnitsxr56 commented Jan 17, 2019 Like 1 reply Follow Share yes i too got confused seeing that !! but slides are top notch Subarna Das commented Jan 17, 2019 Like 2 reply Follow Share @MiNiPanda, that'll be $\dfrac{1}{2x}$ -- typing mistake ben10 commented Jan 17, 2019 Like reply Follow Share Great...Thanks all of you sir. Learner_jai commented Jan 18, 2019 Like reply Follow Share @Arjun Sir, Is this correct interpretation. 2.L = { | L(M) has at most 10000 strings} Lyes=lang having <= 10000 string Lno= any lang having more than 10000string 3.L = { | (L(M) is finite} yes= lang contain finite no of strings no= any lang contain infinite lang 3.L = { | L(M) = Σ* } Lyes=? Lno=? 4.L = { | L(M) is infinite} yes= lang which produce infinite string no= any lang having finite no of strings. 5.L = { | L(M) is recursive} Arjun commented Jan 20, 2019 Like 2 reply Follow Share You can see the complete slides now and ask if anything is not clear. Swapnil Naik commented Jan 20, 2019 Like 1 reply Follow Share Thank you, lots of things got clear! parabol commented Jan 21, 2019 i edited by parabol Jan 21, 2019 Like reply Follow Share @Arjun Sir, My understanding is that, membership problem for a language is undecidable, if we cannot write an yes/no algorithm for checking the membership of a string in that language (such a language should be 'not RE' right ?). If a language is RE, then there exist a TM (algorithm) that would surely say at least 'yes', if that string is present in the language. My doubt is, consider this: L = {<M> | L(M) has at least 10000 strings} (slide 17) , this means that , L is the set of all TM's which accept at least 10000 strings. So, if it is RE , then there should exist an algorithm for checking that condition , i.e we could recursively enumerate all TM's which satisfies this condition. That is , Should it be semi-decidable ? I cannot understand how is it undecidable. Also, I cannot understand how it is different from the semi-decidable problem of 'halting problem' . Here , we could simulate 'M' on a universal TM and check if a TM contains 10000 strings(dovetailing can be used for simultaneous executions) . So UTM would say 'yes' for all the TM's which satisfies this condition. We have an algorithm that at least say 'yes' right ? How is it undecidable ? I cannot understand where I am going wrong. Please help. Aakash_ commented Jan 21, 2019 Like reply Follow Share love you sir and great work Subarna and Sukanya. Thanks a lot. Abhisek Tiwari 4 commented Jan 21, 2019 Like reply Follow Share its really great thanks @Arjun @Subarna Das @Sukannya Ma'am one doubt slide 30 eg of Trivial property "L(M) can be accepted by TM with even no of states" ==>do mean 2 state universal TM having multi-tape with stay option?? Raj Singh 1 commented Jan 22, 2019 i edited by Raj Singh 1 Jan 23, 2019 Like reply Follow Share Hi, I was referring this ( https://gatecse.in/rices-theorem/) post on Rice theorem by Arjun sir. The Rice I theorem is given as: Any non-trivial property of the LANGUAGE recognizable by a Turing machine (recursively enumerable language) is undecidable Then in problem, it says: $L(M)$ has at least 10 strings We can have $T_{yes}$ for $Σ^∗$ and $T_{no}$ for $ϕ$. Hence, L={M∣L(M) has at least 10 strings} is not Turing decidable (not recursive). The theorem talks about recursively enumerable language and empty language $\phi$ is not recursively enumerable (just checked in Ullman). So, is it correct to consider $\phi$ during answer? (Even the slides do consider $\phi$) Shaik Masthan commented Jan 23, 2019 Like reply Follow Share ϕ is a Regular language then it should be Recursive enumerable language, right @raj+singh Raj Singh 1 commented Jan 23, 2019 Like 1 reply Follow Share @Shaik Ullman says on page 362: $L_e$ is not RE It defines $L_e=\{M | L(M) = \phi\}$ I guess this is different from $L=\phi$ and $\phi$ is regular. Seems that I unnecessarily got confused. Right? suniljha commented Jan 23, 2019 i edited by suniljha Jan 23, 2019 Like reply Follow Share @Arjun sir @Subarna Das while doing reductions,A<=B does A follows properties of B or B follows properties of A.These are from same slides. Astha Sharma 2 commented Jan 23, 2019 Like reply Follow Share L(M) is not regular. How is it non monotonic? L(M) is not regular ---YES case will have all languages except regular languages and NO case will have languages which are not (not regular) i.e. regular. but Yes case is not a subset of no case. Then how non monotonic? where am i going wrong please correct! Arjun commented Jan 23, 2019 Like 1 reply Follow Share @Astha Take ANY ONE "yes" case and any one "no" case and see if you can get the SUBSET relation. Deepanshu commented Jan 23, 2019 Like 1 reply Follow Share Arjun sir plzz make blog how to avoid lil mistakes and different startegies to try perfection what we will do in exam .....means those we dont know dont care but sometimes the questions we know we are making mistakes so if there are 70% ques i know prefectly then only 50% -60 % of them are correct 10- 20 % everytime mistake ....plzz add something to avoid mistakes Astha Sharma 2 commented Jan 23, 2019 Like reply Follow Share Ok sir... so can I say that a^nb^n being a non regular language (Here, YES case) is a subset of (a+b)*--regular (NO case) . So, non monotonic and hence not even semi decidable? Arjun commented Jan 23, 2019 Like reply Follow Share Exactly Raj Singh 1 commented Jan 23, 2019 Like reply Follow Share Can someone help me understand examples on slide page 23. Not able to get meaning of solutions. For example: L = { <M> | L(M) = {}] - We can say “no” is M accepts some string, but can we every say “yes” as we need to check infinite number of strings? Learner_jai commented Jan 24, 2019 Like reply Follow Share @Arjun Sir,Thanks a lot SameekshaGupta commented Jan 25, 2019 Like reply Follow Share One doubt regarding Slide no. 30 : Some trivially decidable properties L = {<M> | L(M) is countable} --> for this language is it correct to argue that since we have diagonalisation procedure, so this problem becomes decidable? Arjun commented Jan 25, 2019 Like 1 reply Follow Share How diagonalization helps in deciding that? Actually any recursively enumerable language is countable and that is why it becomes a trivial property (Answer is always yes irresepective of the given TM) Diagonalization proves that there are languages which are not recursively enumerable. SameekshaGupta commented Jan 25, 2019 Like reply Follow Share Ok sir..got it now. All RE languages and Recursive languages have some enumeration procedure for them and the ones which don't have are non-RE. tusharp commented Jan 27, 2019 Like reply Follow Share @Arjun sir confused in this one (https://gateoverflow.in/83694/turing-machine). Understood your answer given there but here can't we create Tyes= {epsilon} Tno= {a,aa,aaa...} ? For semi-deciding we can say, we may consider a TM having initial state as final state. So for yes instance it can output Yes but cannot say for any NO instance. Arjun commented Jan 27, 2019 Like 1 reply Follow Share Does a given TM accepts empty string? Does any TM accepts empty string? These two are different right? The question there is for the second one. For 1, what you told is correct. Utkarsh Joshi commented Apr 1, 2019 Like reply Follow Share So the capability of moving back is responsible for TM to loop forever. And as PDA and DFA can do computations only for as many steps as the number of symbols in the input, they can run for EXACTLY |w| steps and will surely stop at some point and will never loop forever. is it correct reasoning? Arjun commented Apr 1, 2019 Like 1 reply Follow Share Yes for DFA. For PDA slight more change is required to be precise. 0xprateek commented Mar 28, 2022 Like reply Follow Share @arjun sir, Thanks for this slide. Its very very helpfull for understanding decidability. Please log in or register to add a comment.