381 views
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  _______ ?

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)

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

by

Are you saying that decidable means NOT RE?

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

1
819 views
1 vote