The most confusing yet interesting topic is presented here by me. The simple way to solve any decidability question is by logical intuition or analogy. I am going to help you build that in this post. Specials thanks to Arjun Suresh sir for the practice problems (Links to practice problems are provided at the end of the post).
Things to know before we start:
Recursive Language (Decidable) - Both 'yes' and 'no'
Recursively Enumerable Language (Semi-decidable) - Only 'yes'
Not Recursively Enumerable Language (Un-decidable) - No 'yes'
--------------------------------------------------------------------------------------------------------------------------
Shortly i will explain what do we mean by 'yes' and 'no'.
Let's start solving few simple problems first.
Q1) Language(L) = { M is a turing machine that accepts strings of length exactly two }
Soln) Now take any string, say "abcd". Here string length is 4. Now let's start scanning the string from 1st character to the last character.
After scanning first character 'a' of the string "abcd", the Turing machine will conceive that string length is 1. But can it say a 'yes' for the given statement ? i.e. yes this string "abcd" will be accepted by the turing machine that accepts string of length 2 only. Unfortunately the turing machine can't say a 'yes' because the string length is currently 1 but in future there is a possibility that another character might add up enhancing the length of the string to 2.
Now let's scan the second character 'b' of the string "abcd", the Turing machine will conceive that string length is 2. But can it say a 'yes' for the given statement ? i.e. yes this string "abcd" will be accepted by the turing machine that accepts string of length 2 only. Here you might think that as the length of the string at this point is 2 which is also conceived by the Turing machine, so the Turing machine will accept the string. But what if another character comes in future ? It will definitely make the string length 3 which will not be accepted by the given Turing Machine. So here also, the turing machine can't say a 'yes'.
Now after scanning the third character, i.e. 'c' of the string "abcd", the Turing machine will conceive that string length is 3. So you can easily say a 'no' now, i.e. no the given turing machine will not accept the string. Here we can stop our turing machine.
But our problem was to stop the turing machine at a 'yes', i.e. yes the turing machine stops for the given string, but unfortunately we couldn't do that during our scan.
Whenever you can't find a 'yes' to a given problem or statement then as defined earlier, it would be not- recursively enumerable language and hence un-decidable.
--------------------------------------------------------------------------------------------------------------------------
Q2) Language(L) = { M is a turing machine that accepts strings of length greater than equal to two }
soln) Now let's take the same string, "abcd". Here string length is 4. Now let's start scanning the string from 1st character to the last character.
After scanning first character 'a' of the string "abcd", the Turing machine will conceive that string length is 1. But can it say a 'yes' for the given statement ? i.e. yes this string "abcd" will be accepted by the turing machine that accepts string of length greater than equal to 2. Unfortunately the turing machine can't say a 'yes' because the string length is currently 1 but in future there is a possibility that another character might add up enhancing the length of the string.
Now let's scan the second character 'b' of the string "abcd", now the turing machine will conceive that string length is 2. Here the turing machine can say a 'yes', i.e. yes the string will be accepted by the given turing machine. This is because how many characters you add up after this it will always be greater than 2 and hence our turing machine should accept it as per given criterion. So, one can stop the turing machine here.
Whenever you find a 'yes' then check for 'no'. Let's take a simple string "g". Here string length is 1. After scanning the first character 'g' of the string "g", the turing machine will conceive that string length is 1. Can it say a 'no' ? Unfortunately the turing machine can't say a 'no' because in future another character might be there which would add up to make the length of the conceived string 2 and hence accepted by the turing machine.
Whenever you find a 'yes' to a given problem or statement and can't find a 'no' for the same problem then as defined earlier, it would be recursively enumerable language and hence semi-decidable.
--------------------------------------------------------------------------------------------------------------------------
Q3) Language(L) = { M is a turing machine and M halts on string X within 2 steps }
soln) Let string X be "ab". We say M halts on string X whenever M reaches the end of the string.
Clearly just after 2 steps we can easily say that 'yes' the string halts on M within 2 steps.
Now we have our 'yes'. We will now search for 'no'.
Let string X be "abcd". Here after 2 steps only character 'a' and 'b' would have been parsed but not character 'c' and 'd'. So we are still in the middle of the string without reaching the end. So here the Turing machine M can easily reject the string "abcd", i.e. it can say a 'no'.
Whenever you find a 'yes' to a given problem or statement and also a 'no' for the same problem then as defined earlier, it would be recursively language and hence Decidable.
--------------------------------------------------------------------------------------------------------------------------
Additional Tips:
1. In some books semi-decidable and undecidable terms are treated equally. So see what question asks and the answer.
2. Try to go through the above 3 examples 3-4 times so that you get the intuition behind it. Once you get the logic right, practice additional problems given below using this logic.
3. In some problems you might fail to put your logic because of complexity in understanding of the statements, but there are only a few of them, you can easily memorise them.
4. Don't leave this easy topic, just spend 3 hours in this topic. You will be master at it then.
--------------------------------------------------------------------------------------------------------------------------
Problems to practice from:
http://www.cs.rice.edu/~nakhleh/COMP481/final_review_sp06_sol.pdf
https://gatecse.in/rices-theorem/
--------------------------------------------------------------------------------------------------------------------------
Incase of doubt,post a comment here. I will try to reply asap!!!
Things to know before we start:
Recursive Language (Decidable) - Both 'yes' and 'no'
Recursively Enumerable Language (Semi-decidable) - Only 'yes'
Not Recursively Enumerable Language (Un-decidable) - No 'yes'
--------------------------------------------------------------------------------------------------------------------------
Shortly i will explain what do we mean by 'yes' and 'no'.
Let's start solving few simple problems first.
Q1) Language(L) = { M is a turing machine that accepts strings of length exactly two }
Soln) Now take any string, say "abcd". Here string length is 4. Now let's start scanning the string from 1st character to the last character.
After scanning first character 'a' of the string "abcd", the Turing machine will conceive that string length is 1. But can it say a 'yes' for the given statement ? i.e. yes this string "abcd" will be accepted by the turing machine that accepts string of length 2 only. Unfortunately the turing machine can't say a 'yes' because the string length is currently 1 but in future there is a possibility that another character might add up enhancing the length of the string to 2.
Now let's scan the second character 'b' of the string "abcd", the Turing machine will conceive that string length is 2. But can it say a 'yes' for the given statement ? i.e. yes this string "abcd" will be accepted by the turing machine that accepts string of length 2 only. Here you might think that as the length of the string at this point is 2 which is also conceived by the Turing machine, so the Turing machine will accept the string. But what if another character comes in future ? It will definitely make the string length 3 which will not be accepted by the given Turing Machine. So here also, the turing machine can't say a 'yes'.
Now after scanning the third character, i.e. 'c' of the string "abcd", the Turing machine will conceive that string length is 3. So you can easily say a 'no' now, i.e. no the given turing machine will not accept the string. Here we can stop our turing machine.
But our problem was to stop the turing machine at a 'yes', i.e. yes the turing machine stops for the given string, but unfortunately we couldn't do that during our scan.
Whenever you can't find a 'yes' to a given problem or statement then as defined earlier, it would be not- recursively enumerable language and hence un-decidable.
--------------------------------------------------------------------------------------------------------------------------
Q2) Language(L) = { M is a turing machine that accepts strings of length greater than equal to two }
soln) Now let's take the same string, "abcd". Here string length is 4. Now let's start scanning the string from 1st character to the last character.
After scanning first character 'a' of the string "abcd", the Turing machine will conceive that string length is 1. But can it say a 'yes' for the given statement ? i.e. yes this string "abcd" will be accepted by the turing machine that accepts string of length greater than equal to 2. Unfortunately the turing machine can't say a 'yes' because the string length is currently 1 but in future there is a possibility that another character might add up enhancing the length of the string.
Now let's scan the second character 'b' of the string "abcd", now the turing machine will conceive that string length is 2. Here the turing machine can say a 'yes', i.e. yes the string will be accepted by the given turing machine. This is because how many characters you add up after this it will always be greater than 2 and hence our turing machine should accept it as per given criterion. So, one can stop the turing machine here.
Whenever you find a 'yes' then check for 'no'. Let's take a simple string "g". Here string length is 1. After scanning the first character 'g' of the string "g", the turing machine will conceive that string length is 1. Can it say a 'no' ? Unfortunately the turing machine can't say a 'no' because in future another character might be there which would add up to make the length of the conceived string 2 and hence accepted by the turing machine.
Whenever you find a 'yes' to a given problem or statement and can't find a 'no' for the same problem then as defined earlier, it would be recursively enumerable language and hence semi-decidable.
--------------------------------------------------------------------------------------------------------------------------
Q3) Language(L) = { M is a turing machine and M halts on string X within 2 steps }
soln) Let string X be "ab". We say M halts on string X whenever M reaches the end of the string.
Clearly just after 2 steps we can easily say that 'yes' the string halts on M within 2 steps.
Now we have our 'yes'. We will now search for 'no'.
Let string X be "abcd". Here after 2 steps only character 'a' and 'b' would have been parsed but not character 'c' and 'd'. So we are still in the middle of the string without reaching the end. So here the Turing machine M can easily reject the string "abcd", i.e. it can say a 'no'.
Whenever you find a 'yes' to a given problem or statement and also a 'no' for the same problem then as defined earlier, it would be recursively language and hence Decidable.
--------------------------------------------------------------------------------------------------------------------------
Additional Tips:
1. In some books semi-decidable and undecidable terms are treated equally. So see what question asks and the answer.
2. Try to go through the above 3 examples 3-4 times so that you get the intuition behind it. Once you get the logic right, practice additional problems given below using this logic.
3. In some problems you might fail to put your logic because of complexity in understanding of the statements, but there are only a few of them, you can easily memorise them.
4. Don't leave this easy topic, just spend 3 hours in this topic. You will be master at it then.
--------------------------------------------------------------------------------------------------------------------------
Problems to practice from:
http://www.cs.rice.edu/~nakhleh/COMP481/final_review_sp06_sol.pdf
https://gatecse.in/rices-theorem/
--------------------------------------------------------------------------------------------------------------------------
Incase of doubt,post a comment here. I will try to reply asap!!!
LET "M" BE A TURING MACHINE
ReplyDelete1. "M ACCEPTS A STRING OF LENGTH 2014"- IT IS RECURSIVE ENUMERABLE
2. "M IS A TURING MACHINE THAT ACCEPTS STRINGS OF LENGTH EXACTLY 2"- IT IS NON RE
for me both the problem is NON-RE...CAN U PLEASE EXPLAIN IT!!!!!!!!!!!!!!!!!!!!!!!
yes you are absolutely correct. but remember here there is no bound on the symbols/alphabets used. If you put a bound on the input alpabet, say SIGMA = {a,b} then there would be only finite number of strings of length 2014. SO you can say a yes. but you can't say a no because for a shorted string there is a chance that one more character might add up in future. As explained above
DeleteAccording to you,what will be the answer for below problem and WHY????????
Delete"Let be the encoding of a Turing machine as a string over ∑= {0, 1}. Let L = { |M is a Turing machine that accepts a string of length 2014 }. Then, L is RE or NON RE????
THANK YOU..
Recursively enumerable....
DeleteIf ∑= {0, 1}. would not have been given then it would be Non Recursively enumerable...
A simple real life example for you. Suppose i give you two characters 'a' and 'b'. Now i imagined a 4 letter word made up of character 'a' and 'b' only, and then ask you to guess it. So you can easily guess it by trying all possible combinations of 'a' and 'b' for 4 letter words...like "aaaa", "aaab"....so on. There will be total 2^4 permutations possible. So just by checking 2^4 = 16 permutations you can easily guess my word.
DeleteNow if you don't know the characters what will you do. The word might be made up of any random characters...greek characters, local language characters, mathematical characters or any other... There is no way you can try all possible combinations and be sure that you can guess the word i have imagined unlike previous case.
thank you for your valuable time and effort.....
Deletecan you please help me with below concept!!
ReplyDelete1.please explain "write through" and "write back" protocol in terms of "read(hit and miss)" and "write(hit and miss)"...........how to transfer the blocks from DRAM to Cache and also avg access time in both the cases.(write through_write_back_math)
2.please follow mathematical notation; I am really confused with the theory portion..
3.you can also take the help of following example to explain this concept->
A 64 word Cache and Main Memory are divided into 16 word blocks...cache access time=10 ns ,,MM access time =50 ns. the hit ratio for read operation is =80% and write operation=90%
whenever a page fault occurs,the associated block must be brought from Main memory to cache for both read and write operation....read frequency=40%,write frequency =60%
1.what is avg access time if write through scheme is used?
2.what is avg access time if write back scheme is used?
Your question was incomplete a bit. i have modified it.
Deletehttps://iamruturaj.blogspot.com/2018/07/cache-writing-schemes.html
Hi bhaiya I am Pratik Hope you are well,
ReplyDeleteHow to deal with the following statements to check for decidability:
"L1={⟨M⟩∣M takes at least 2016 steps on some input} ,
L2={⟨M⟩∣M takes at least 2016 steps on all inputs} and"
In L2 the statement is decidable as per the answer key
But bhaiya I want to know if we are supposed to check all string in domain how can L2 be a decidable language
Sorry it's been long time !!! I hardly remember anything now !!! That's why i wrote it that time, because i knew i would forget. Don't worry much, understand the basics and skip it. Don't go to extreme depth of this topic.
DeleteOkay Bhaiya, thanks for reply :)
Delete