halting-problem

Consider the following languages. $$\,\,\,\,\,\,\,\,\,\,\,\,$$ $${L_1} = \left\{ {\left\langle M \right\rangle |M} \right.$$ takes at least $$2016$$ steps on some input $$\left. \,...

Which of the following problems are decidable? $$1.$$ Does a given program ever produce an output? $$2.$$ If L is a context-free language, then, is $$\overline L $$ also context-fr...

Define Languages $${L_0}$$ and $${L_1}$$ as follows $${L_0} = \left\{ { < M,\,w,\,0 > \left| {M\,\,} \right.} \right.$$ halts on $$\left. w \right\}$$ $${L_1} = \left\{ { < M,w,1 >...

Given the programming constructs: (i) assignment (ii) for loops where the loop parameter cannot be changed within the loop (iii) if-then-else (iv) forward go to (v) arbitrary go to...

Which of the following statements is false?