0 votes 0 votes L= {(M)| M is a TM and there exists an input w, |w| < 100, on which M halts}. Is L decidable? Please explain. Theory of Computation made-easy-test-series theory-of-computation decidability + – agoh asked Dec 8, 2016 • edited Mar 4, 2019 by akash.dinkar12 agoh 470 views answer comment Share Follow See 1 comment See all 1 1 comment reply agoh commented Dec 8, 2016 reply Follow Share My approach has been: We can enumerate words st |w| <100. Let there be a machine M which rejects all inputs of len > 100. while(true): { i = 1 for w in set of words of len <100: { do i steps on machine M if M halts on w (accept/reject), return "yes" } i = i+10 } But here M might loop forever, because number of steps has no upper bound. What is the correct way to do this? Answer is decidable. 0 votes 0 votes Please log in or register to add a comment.
0 votes 0 votes Answer is : Not even partially Decidable i.e not even Turing Recognizable Apply Rice Theorem. The property TM accept Language of less than 100 strings is Non Trivial and also Non Monotonic. Therefore it's not even Partially Decidable. Mehak Sharma 1 answered Dec 17, 2016 Mehak Sharma 1 comment Share Follow See all 0 reply Please log in or register to add a comment.
0 votes 0 votes Testing any property of the language recognized by TM is undecidable. reena_kandari answered Dec 30, 2016 reena_kandari comment Share Follow See all 0 reply Please log in or register to add a comment.