In the worst case scenario I would run one TM for each string as we have finite number of strings.

The Gateway to Computer Science Excellence

0 votes

So, this question is taken from here

https://gateoverflow.in/151057/langle-rangle-there-exist-input-whose-length-than-which-halts%24

$L=\{<M>| $M is a Turing machine and there exists an input whose length is less than 100 on which M halts$\}$

I got to know that for semi-decidability, since we have finite number of strings of length less than 100, for all such strings, we run TM in interleaved mode and if for any input TM halts, we say Yes.But my question is, for how long will we wait?

Suppose TM may take too long before it says yes, can we be sure whether we are really reaching an answer or TM has got into infinite loop?

0

It should be accepting the strings of that language. If we give any string other than the language it may or may not halt i.e. recursively enumerable.

In the worst case scenario I would run one TM for each string as we have finite number of strings.

In the worst case scenario I would run one TM for each string as we have finite number of strings.

0

For running in interleaved mode they use $dovetailing$.

I don't know what the process does. You can chek it here

Similar ques : https://gateoverflow.in/72527/re-language-interleaved-mode

0

yes RE, $\epsilon \subset \Sigma ^{*}$. So, 2nd Rice theorem not applicable here

https://gatecse.in/rices-theorem/

this one too RE

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

50,654 questions

56,169 answers

193,878 comments

94,301 users