332 views
0 votes
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?

Please log in or register to answer this question.

Related questions

0 votes
0 votes
0 answers
3
Na462 asked Jan 21, 2019
720 views
0 votes
0 votes
0 answers
4
Ayush Upadhyaya asked Jan 13, 2019
407 views
From http://www.cs.rice.edu/~nakhleh/COMP481/final_review_sp06_sol.pdf $L_{26}=\{<M>|$ M is a TM such that both L(M) and $\lnot L(M)$ are infinite $\}$I was unable to get...