4 votes 4 votes Consider the following language over Σ = {0, 1}:L = {<M>|M is TM that accept all strings of length at most 5} Which of the following is true? (A) Decidable and REC (B) Undecidable and RE (C) Undecidable and non RE (D) Decidable but RE Theory of Computation theory-of-computation turing-machines decidability madeeasy-testseries-2018 + – Bhavya Bhatia asked Jan 11, 2018 edited Mar 5, 2019 by ajaysoni1924 Bhavya Bhatia 2.3k views answer comment Share Follow See all 17 Comments See all 17 17 Comments reply Bhavya Bhatia commented Jan 11, 2018 reply Follow Share Answer is given as (C), but shouldn't this be decidable as we can stop the Turing machine after 5 steps and tell whether the language has been accepted or not ? Can't we think like this ? Please Answer @Arjun Sir 0 votes 0 votes SHUBHAM SHASTRI commented Jan 11, 2018 reply Follow Share yes answer is correct....that is C... we can provide all 5 length strings ..but what will be decidable here???... whether the TM is able to accept string within 5 steps or not ... but what question says that 5 length string accepted or NOT.... so we cant say this....because no one can say..is given string valid as per language... if its valid we cant say how many steps it may take ....and after how many moves TM halts.. if strings provided are not from L then TM will never halt... 4 votes 4 votes Bhavya Bhatia commented Jan 11, 2018 i edited by Bhavya Bhatia Jan 11, 2018 reply Follow Share @SHUBHAM Thanks for this explanation., But can you explain why it is non RE, a TM is available for this and we can write a program for the TM to accept all the strings which belong to {0,1} with length atmost 5 0 votes 0 votes stanchion commented Jan 22, 2018 reply Follow Share @ SHUBHAM SHASTRI It is Undecidable for sure but how to decide for RE or not? 0 votes 0 votes Aakanchha commented Jan 28, 2018 reply Follow Share same query how are wedeciding its RE or not? 0 votes 0 votes akshat sharma commented Jan 28, 2018 reply Follow Share it is undecidable and non RE this link will clear doubt answer will be C explanation : from this link second point https://www.cs.rice.edu/~nakhleh/COMP481/final_review_sp06_sol.pdf L2 = {hMi|M is a TM and |L(M)| ≤ 3}. – Not RE. We prove this by a reduction from HP. τ (hM, xi) = hM0 i. M0 on input w: it erases its input, copies M and x to its tape, and runs M on x; it accepts if M halts on x. We now prove the validity of reduction: ∗ hM, xi ∈ HP ⇒ M does not halt on x ⇒ M0 does not accept any input ⇒ |L(M0 )| ≤ 3 ⇒ M0 ∈ L2. ∗ hM, xi ∈/ HP ⇒ M halts on x ⇒ M0 accepts all inputs ⇒ |L(M0 )| > 3 ⇒ M0 ∈/ L2. 0 votes 0 votes Mk Utkarsh commented Sep 16, 2018 reply Follow Share akshat sharma but the problem you pointed out is not the same, the problem pointed out by you, $L_2 = \left \{ \langle M \rangle | M \ is \ a \ TM \ and | L(M) | \leq 3 \right \}$ means $L_2$ is a language which consists of input $\langle M \rangle$ on condition that M is a TM and cardinality of language of M is less than 3. It has nothing to do with string length. 0 votes 0 votes Chaitrasj commented Dec 20, 2018 reply Follow Share The TM has to accept only those strings whose length is atmost 5, so here there are 2 conditions to be satisfied by a valid TM for this language, first it must accept all such strings whose length is within 5, and second it should not accept any other string whose length is greater than 5. Since asking a TM whether it will accept a specific string is membership problem and even if a TM satisfies first condition, we cannot put it in output, because there is no logic to check for second condition, we need to keep checking infinitely to make sure TM doesn't accept any string of length greater than 5. So in short this becomes Not RE because we cannot collect the valid TM's in output 0 votes 0 votes Ayush Upadhyaya commented Jan 3, 2019 reply Follow Share Let me know if below is correct and reasonable (1)Since, this property is non-trivial property of the Language accepted by the Turing machine, the language is Undecidable. (2)Now, Applying Rice's theorem part 2 $T_{yes}=\phi$ and $t_{no}=\sum^*$ and $T_{yes} \subset T_{no}$, so it is NOT RE. 0 votes 0 votes uploadalltoit commented Jan 17, 2019 reply Follow Share it should be RE and undecidable RE L is a set of all TMs : {TM1,TM2,TM3,........} Now, run each TM for a fixed amount of time and stop it give chance to next one. Do this for each TM, after a certain amount of time the for strings with length<=5 TM will halt and rest will run forever. This way we hv an enumeration method so its RE. But since we cannot stop it for each string its undecidable. 3 votes 3 votes TUSHAR_BHATT commented Aug 30, 2019 reply Follow Share @Ayush Upadhyaya shouldn't Tyes intersect Tno be phi? 0 votes 0 votes TUSHAR_BHATT commented Dec 2, 2019 reply Follow Share @Mk Utkarsh is this RE ?? 0 votes 0 votes toxicdesire commented Dec 2, 2019 reply Follow Share No, Tushar, It's proper subset. $T_{yes} \subset T_{no}$ And $\phi$ is a proper subset of any non-empty set, and improper subset of empty set. So, Ayush's reasoning is correct. 0 votes 0 votes TUSHAR_BHATT commented Dec 2, 2019 reply Follow Share https://gateoverflow.in/7427/which-following-languages-recursively-enumerable-language?show=14134#c14134 see this @toxicdesire 0 votes 0 votes TUSHAR_BHATT commented Jan 17, 2020 reply Follow Share Okay I was confused because of "atmost" now clear :) 0 votes 0 votes LakhanMalviya commented Jan 24, 2020 reply Follow Share the answer right by rice theorem 0 votes 0 votes roh commented Jul 16, 2020 reply Follow Share If the above language is NOT RE, then how the below https://gateoverflow.in/151057/langle-rangle-there-exist-input-whose-length-than-which-halts%24 is RE? Please clarify. 0 votes 0 votes Please log in or register to add a comment.