The Gateway to Computer Science Excellence

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

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.

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

@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

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

- All categories
- General Aptitude 1.9k
- Engineering Mathematics 7.5k
- Digital Logic 2.9k
- Programming and DS 4.9k
- Algorithms 4.4k
- Theory of Computation 6.2k
- Compiler Design 2.1k
- Databases 4.1k
- CO and Architecture 3.4k
- Computer Networks 4.2k
- Non GATE 1.4k
- Others 1.4k
- Admissions 595
- Exam Queries 573
- Tier 1 Placement Questions 23
- Job Queries 72
- Projects 18

50,737 questions

57,321 answers

198,391 comments

105,142 users