1 votes 1 votes Decidable or Undecidable? Given a Turing machine M, a string s and an integer k, M accepts s within k steps. Please elaborate. Theory of Computation decidability theory-of-computation turing-machine recursive-and-recursively-enumerable-languages + – Mizuki asked Nov 14, 2018 Mizuki 496 views answer comment Share Follow See all 0 reply Please log in or register to add a comment.
Best answer 2 votes 2 votes It is decidable as it will stop after K steps whatever K might be,halting machine is recursive hence decidable sripo answered Nov 14, 2018 selected Nov 14, 2018 by Mizuki sripo comment Share Follow See all 3 Comments See all 3 3 Comments reply Mizuki commented Nov 14, 2018 reply Follow Share @sripo so we are not interested in ~absolute acceptance of s, but only in k steps? 0 votes 0 votes sripo commented Nov 14, 2018 reply Follow Share Decidablity means if the there will be a solution or not,we are not interested in absolute acceptance of s,if we know that in k steps we will get to reach a state where there will be an acceptance or not means it is decidable.Decidable does not mean getting right solution always. 1 votes 1 votes Mizuki commented Nov 14, 2018 reply Follow Share @sripo That was really helpful. Thank you! 0 votes 0 votes Please log in or register to add a comment.
0 votes 0 votes According to me the language is undecidable. Reason being machine will accept the string in “k” steps and will halt but when rejecting it can/ cannot halt. Hence clearly partially decidable. But since they asked about decidable/undecidable so I will conclude it undecidable. rish1602 answered Sep 16, 2021 rish1602 comment Share Follow See all 0 reply Please log in or register to add a comment.