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
ϕ is a Regular language then it should be Recursive enumerable language, right @raj+singh
@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?
@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 Take ANY ONE "yes" case and any one "no" case and see if you can get the SUBSET relation.
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
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?
@Arjun Sir,Thanks a lot
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 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.
These two are different right? The question there is for the second one. For 1, what you told is correct.