The Gateway to Computer Science Excellence
+2 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
in Theory of Computation by (479 points)
edited by | 880 views
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
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 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...
@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


It is Undecidable for sure but how to decide for RE or not?

same query how are wedeciding its RE or not?

it is undecidable and non RE  this link will clear doubt 

answer will be C explanation : from this link second point

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.


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. 

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

it should be RE and undecidable 


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.


@ shouldn't Tyes intersect Tno be phi?


 @ is this RE ??

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.
Okay I was confused because of "atmost" now clear :)
the answer right by rice theorem

Please log in or register to answer this question.

Related questions

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,737 questions
57,324 answers
105,169 users