0 votes 0 votes 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 Theory of Computation rice-theorem theory-of-computation decidability theorem rice + – hem chandra joshi asked Dec 1, 2017 hem chandra joshi 1.1k views answer comment Share Follow See all 12 Comments See all 12 12 Comments reply Anu007 commented Dec 1, 2017 reply Follow Share suppose you run TM for 10 steps; if it halt in 10 steps you can say yes; if it is not halt then you can say no , so means you can decide then why undeciadable. 1 votes 1 votes hem chandra joshi commented Dec 1, 2017 reply Follow Share what i assume in first case it halt and other one it is in loop . Now So it is undecidable? @Anu007 plz describe means of Trivial and non-trivial in terms of rice theorem and monotonic and non-monotonic also. 0 votes 0 votes Anu007 commented Dec 1, 2017 reply Follow Share you can run on same machine and if you say yes and no then decidable. Trivial : If all TM behave same for any property. like machine has 2 states, Non trivial: ALL Tm does not behave same for Any property. 1 votes 1 votes srestha commented Dec 1, 2017 reply Follow Share trivial means it accepts every string of that language non trivial means it accepts some string of that language but not all 0 votes 0 votes hem chandra joshi commented Dec 1, 2017 reply Follow Share @srestha so you want to say that Trivial means :: L(G) = 0*1* than all strings (phi,0,1,00,11 ....etc) is accepted by TM Non Trivial Means :: while for this language some strings is accepted by TM like (phi,0,1) only other are rejected . Rt? 0 votes 0 votes hem chandra joshi commented Dec 1, 2017 reply Follow Share @Anu007 reference to above question , I am asking you As in first Turing Machine it is halting in 10 steps while in second it is not halt in 10 steps so I think this is non-trivial property ? 0 votes 0 votes hem chandra joshi commented Dec 1, 2017 reply Follow Share Also tell what is meant by monotonic and non-monotonic means ? 0 votes 0 votes srestha commented Dec 1, 2017 reply Follow Share not like that Turing Machines halt within 10 steps it is TM property. So, TM property is always trivial non trivial case are the case which we examine for the language of TM like language has atleast 10 states.....etc 2 votes 2 votes Manu Thakur commented Dec 7, 2017 reply Follow Share yep! @srestha said correctly! Rice's theorem is meant to be applied on the language but not on the properties of a Turing machine, in this case whether a TM halts with in 10 steps or not is a property of a TM and we can answer this question either yes or no always in finite time. 3 votes 3 votes srestha commented Dec 8, 2017 reply Follow Share thanks :) 2 votes 2 votes srestha commented Dec 8, 2017 reply Follow Share @ Manu Thakur how r u searching question? I mean how u find 6 days previous question? 0 votes 0 votes Manu Thakur commented Dec 8, 2017 reply Follow Share @srestha i didn't search, this post was in the recent activities, but don't know how :D 1 votes 1 votes Please log in or register to add a comment.