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.

in Theory of Computation by Boss (29.1k points) | 156 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.

Please log in or register to answer this question.

Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
50,737 questions
57,321 answers
105,142 users