Made Easy Test series

Question

Consider the following language :

P1 : {<M, x, k>| M is a TM and M does not halt on x within k steps}

P2 : {<M>| M is TM and L(M) = $\phi$}

P3 : {<M>| M is a TM and L(M) = finite language}

The number of problems which are not RE is/are  _______ ?

Answer 1

1) - First one Is decidable, as give that string x as input to that turing machine M, and perform k steps of computation, if TM doesn't halt till k steps, then it will be rejected, else accepted. So, it is RE.

2)- L(M) = phi , here we can apply rice theorem, as it is the property of the language accepted by Given TM.

So, first we'll check whether it is a non trivial property or not. Here, this property will not always be true for every TM ,so it is a non trivial property, hence undecidable.

Now, we'll check whether it is a non- monotonic property or not. Here, T(yes) which is phi and T(no) which can be any non empty set of string on given alphabet let say {1,2} . Here, T(yes) is a proper subset of T(no), so it is a non- monotonic property, hence not even semi- decidable .( Not RE) 

3)- Here also we can apply rice theorem, as it is a property of language accepted by TM.

This is a non trivial property, as it will not always be true for every TM possible, hence undecidable.

This is also a non- monotonic property , as T(yes) let's say be {2,4} and T(no) be {set of even postive integers} , here T(yes) is a proper subset of T(no) ,so it is a non-monotonic property, hence not even semi- decidable, (not RE)

Answer 2

According to me, all the three should be NOT RE. 

S1-   its mentioned that machine accepts/rejects string in either more than K steps or infinite steps. Hence its  NOT RE

S2 and S3 are also NOT RE

Comments

Are you saying that decidable means NOT RE?

---

Edited the answer.

No sir, just NOT RE

---

For S1, what's wrong in the decision algorithm given in the accepted answer?

---

Sir,

In the accepted answer for P1 the user mentions that the machine “perform k steps of computation, if TM doesn't halt till k steps, then it will be rejected”. There is an assumption that the machine will be accepting in K steps. 

But, in the question its just given that machine just doesn’t halt on any input within K steps. The machine if accepting will go to more than K steps or infinite or when rejecting will again go to more than K steps or infinite. Hence its undecidable so not recursive enumerable.