Log In
2 votes

Here is my analysis.

P1: When we bound the number of steps a turing machine can tape, the total number of input possible that can be taken by such turing machine becomes finite and by running TM in an interleaved mode I can decide whether TM M halts on x within k steps.

So, P1 is Decidable or REC.

P2: Here I can have two TM for this say $T_{yes}=\{\epsilon,a\}$ and $T_{no}=\{aaa\}$. This is Undecidable, but since we cannot have $T_{yes}$ such that it should be a proper subset of $T_{no}$, this is Recursively Enumerable.So, this RE but not REC.

P3:I can fix the moves of TM to 99, and only $| \sum|^{99}$ inputs are possible. I can run TM on such inputs in an interleaved way and hence I can decide P3.

Hence, P3 is decidable.->REC.

So, I think here answer must be 1.

Please let me know what's right.

in Theory of Computation 283 views
Is it compulsory that 1TM move represents 1 symbol read from input?
1. As first one is bounded it is surely recursive.

3. "There exist" is given if we assume according to given statements that there exists a x 1<x<=100 on which TM halts and will say yes or no. This makes it recursive as we are dealing with that particular x.

2. Rice's theorem part 1 which is correct.

Correct me if my approach is wrong. I am going wrong in most of the examples where Rice's theorem is not applicable and reduction is required.
I think P3 is Undecidable because TM may never halt on an input and we cannot say after how much amount of time a TM will whether actually accept that input or reject it.
@Ayush sorry for above comment. I mean option p3 is REL. What I thought is we need to check all strings having length <100 on which it halts. If we consider non deterministic TM eah copy of TM will check for each possible length and even if one of the TM accepts and halts it will say "yes" but if no such string is there, then it will go in infinite loop. Hence REL.


what will be ans

if they ask "M is a TM and M accepts atleast $2$ string of same length"


@srestha-This should be undecidable. Because, it might be possible that on the very first string the TM hangs or loops, you cannot wait for an answer indefinitely.

And since it is a non-trivial property of the language accepted by TM, by Rice's theorem it is Undecidable.



Why to run TM in interleaved mode in P1

If we restrict no of steps of TM to chance that TM will be in infinite loop so we can give input one by one also ..If TM takes Lessthan or equal K steps we reject it and if it take K+1 steps we accept it



For P1 and P3 we can't apply rice theorem as ...rice theorem is applied when we are given properties of languages of TM not properties of TMs  am I right ?..For P3 it is RE but not REC ..we have to use interleaved order?



Also if we are not able to find Tyes and Tno such that Tyes $\subset$ Tno

Then we can't comment about RE / Not RE

L =  {<M> | L(M) is infiinite} is non RE . but we cant find T yes $\subset$  Tno 

Here how you concluded this 

 but since we cannot have TyesTyes such that it should be a proper subset of TnoTno, this is Recursively Enumerable.So, this RE but not REC.


reply to the question:

Your conclusion for P2 is wrong since RICE theorem’s 2nd part is not 2-way.

For @ comment:

I think that will be undecidable but REL, since we can go on checking if for any length we have at least 2 strings getting accepted.

Please log in or register to answer this question.

Related questions

0 votes
0 answers
L1:{<M> | there exist a Turing machine M' such that <M>$\neq$<M'> and L(M) = L(M')} How this problem becomes trivial? and if it non-trivial then please explain why is that so. According to my understanding, non-trivial properties are the one where a language ... and if it is then is it okay to say M1=M2 because they are kind of same machine but other one is just with some non deterministic nature.
asked Oct 30, 2018 in Theory of Computation Swapnil Naik 143 views
0 votes
0 answers
Writes Non Blank: Given a turing machine T, does it ever writes a non-blank symbol on its tape, when started with a blank tape. how the above problem is solvable? somewhere i got this explanation: Let the machine only writes blank symbol. Then its ... this is a non-trivial property of turing machine and every non trivial property of turing machine is undecidable, so this is also undecidable.
asked Sep 21, 2018 in Theory of Computation aambazinga 134 views
2 votes
2 answers
I was Studying About Undecidability on GateCSE. I am facing a doubt that : L = {<M> | M accepts "1"} L is set of String & each String is an Encoding of TM & TM accepts 1 L = {<M> | L(M) = {1}} Given a Input Program we have to see it Accepts 1 & nothing ... selected encoding ?) What really is difference between both of them ? Can you definition of 2 in words like " L is set of String ............"
asked Jan 13, 2018 in Theory of Computation yogi_p 310 views