search
Log In
0 votes
172 views

1.{<M>| M is a TM accepts any string starting with 1}

2.{<M>| M is TM accept exactly 20 strings}

 

Please guide 

I don’t know how to apply rice theorem.

for 1. Is Tyes = { string starting with 1}   Tno = { all strings – strings starting with 1}

  1. what is Tyes and Tno here? I only conclude by intution that when we provide strings as input some got into loop and some got accepts .
in Theory of Computation 172 views
0

@Arjun sir ,   @srestha ma'am please help me ,

0
I think , no rice theorem, nedded here

Ans will be decidable

Is ans given?
1

@Learner_jai the option 2 is decidable as finite number of strings can be accepted by DFA

for option 1. its also decidable since all the strings starting with 1 , can be given by regex 1(0+1)*.

0

@srestha ma'am , question is there in Arjun sir 2nd lecture, I think i need to watch it again, 

 

1

@srestha

The question is about acceptance of strings by TM. Isn't it a membership problem which is undecidable? 

1

  (1)Tyes = { string starting with 1}   Tno = { all strings – strings starting with 1} .yes these statements are right ,and we can conclude that this is non trivial property so this is undecidable.

(2) $L_{yes}=${accept exactly 20 strings(0,1,11,111....)  }

$L_{no}=${0} 

so we can clearly see that these two RE set in which first one satisfy the property and second one doesn't ,so we can conclude that this is non trivial property so this is undecidable.

Please log in or register to answer this question.

Related questions

0 votes
0 answers
1
426 views
Problem : It is undecidable whether an arbitrary Turing Machines halt within 10 steps? Let consider Two Turing machine in which first one it is halt in 10 steps while in other it is not , so as it is undecidable. @arjun sir ,@bikram sir or @others
asked Dec 1, 2017 in Theory of Computation hem chandra joshi 426 views
2 votes
0 answers
2
375 views
L={<M>: M is a TM that accepts all even numbers } Why it is not recursively enumerable language???
asked Jul 18, 2017 in Theory of Computation akb1115 375 views
2 votes
1 answer
3
298 views
If we are not able to apply non-monote property ,then is it always true that it is RE but not REC,are there any scenarios where we can't apply non-monotone property but still language is NOT RE. Say,L={TM| L(TM) has atleast one string}, Now it is clearly Language property ... mean theat RE but not REC. P.S:- By (i) and (ii) ,i mean the definitions mentioned here.(http://gatecse.in/rices-theorem/)
asked Jan 22, 2017 in Theory of Computation rahul sharma 5 298 views
1 vote
0 answers
4
276 views
I need to understand when to apply RICE's theorem and when to not. Questions like:- Turing machine makes at least five moves,It accepts a string input of length atleast five ,TM halts for every input on length <50 are all decidable. But these are NON TRIVIAL properties ... because some TM will say yes and some will say NO.Then why can't we use same concept on above metioned questions? Please help
asked Jan 13, 2017 in Theory of Computation rahul sharma 5 276 views
...