Can't we think like this ?

Please Answer @Arjun Sir

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

0

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

Can't we think like this ?

Please Answer @Arjun Sir

+4

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

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

0

@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

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

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

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

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

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.

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

+1

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.

0

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.

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

- All categories
- General Aptitude 1.9k
- Engineering Mathematics 7.5k
- Digital Logic 2.9k
- Programming and DS 4.9k
- Algorithms 4.4k
- Theory of Computation 6.2k
- Compiler Design 2.1k
- Databases 4.1k
- CO and Architecture 3.4k
- Computer Networks 4.2k
- Non GATE 1.4k
- Others 1.4k
- Admissions 595
- Exam Queries 573
- Tier 1 Placement Questions 23
- Job Queries 72
- Projects 18

50,737 questions

57,324 answers

198,405 comments

105,169 users