The Gateway to Computer Science Excellence

+1 vote

Consider the following language over $\sum=\{0,1\}$

$L=\{<M>|$ M is a turing machine that accepts all strings of length atmost 5 $\}$

Since, this is a non-trivial property of TM, so surely it is undecidable.

Now, Applying Rice’s Theorem part 2, $T_{yes}=\{0,1\}$ and $T_{no}=\sum^*$ and $T_{yes} \subset T_{no}$ so this is NOT RE.

Have I correctly applied property 2?

$L=\{<M>|$ M is a turing machine that accepts all strings of length atmost 5 $\}$

Since, this is a non-trivial property of TM, so surely it is undecidable.

Now, Applying Rice’s Theorem part 2, $T_{yes}=\{0,1\}$ and $T_{no}=\sum^*$ and $T_{yes} \subset T_{no}$ so this is NOT RE.

Have I correctly applied property 2?

0

Since it is the property of Turing Machine and not that of Recursively Enumerable language, I think we can't apply Rice's theorem here. However We can say “no” is M accepts some string, but can we every say “yes” as we need to check infinite number of strings. So it is not Recursively Enumerable. Correct me if I am wrong.

Refer slide 23 https://gateoverflow.in/?qa=blob&qa_blobid=13695039841867827427

0

We can say no when any string is rejected.

We can say yes when M accepts all strings of length 0 to 5. But we cannot determine this as for a string M will halt or not is not known. Hence, undecidable I think.

We can say yes when M accepts all strings of length 0 to 5. But we cannot determine this as for a string M will halt or not is not known. Hence, undecidable I think.

+1

@Aarvi Chawla-No, it is about Language accepted by a turing machine.Here I am not talking about how many states machine M has, or whether it ever makes a left move.Here I am talking about what strings it accepts.So, I can apply Rice's theorem.

+2

Isn't the problem semi-decidable?

As in, the strings which have length atmost 5 are finite. We can list them out. Now all these strings can be inputted to the given TM using dovetailing method. If the TM really accepts all the given strings, we can say yes. If it goes into a loop, we may not be able to say anything. So at least for the yes part, we'll be able to say, isn't it?

+4

I think the part 2 is applied incorrectly as your $T_{no}$ = $\sum^{*}$ also satisfies the given language.

The question is that TM accepts all strings which have length ** atmost 5**. It may or may not accept strings of other lengths which is of no concern to us.

If the question would have been that the TM accepts **only** strings having length atmost 5 then it would be not RE.

- All categories
- General Aptitude 1.8k
- Engineering Mathematics 7.4k
- 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.1k
- Non GATE 1.5k
- Others 1.7k
- Admissions 595
- Exam Queries 576
- Tier 1 Placement Questions 23
- Job Queries 72
- Projects 17

50,666 questions

56,155 answers

193,759 comments

93,732 users