The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
2,811 views

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

posted Jan 16 in Theory of Computation by Veteran (395,471 points)
edited Jan 27 by | 2,811 views
56
Like
17
Love
1
Haha
0
Wow
0
Angry
0
Sad

32 Comments

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!

@Astha Take ANY ONE "yes" case and any one "no" case and see if you can get the SUBSET relation. 

 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

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?
Exactly

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?

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.
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.

@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.

  1. Does a given TM accepts empty string?
  2. 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. 

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?
Yes for DFA. For PDA slight more change is required to be precise.
Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
50,117 questions
53,218 answers
184,619 comments
70,454 users