# TOC-Undecidability

283 views

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.

0
Is it compulsory that 1TM move represents 1 symbol read from input?
0
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.
1
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.
0
0
@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.
0

@Ayush

what will be ans

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

0

@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.

0

Why to run TM in interleaved mode in P1

If we restrict no of steps of TM to K+1...no 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

0

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?

0

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.

0

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.

## Related questions

1
161 views
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.