Decidability

Question

Decidable or Undecidable? Given a Turing machine M, a string s and an integer k, M accepts s within k steps.

Please elaborate.

Answer 1

It is decidable as it will stop after K steps whatever K might be,halting machine is recursive hence decidable

Comments

@sripo so we are not interested in ~absolute acceptance of s, but only in k steps?

---

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.

---

@sripo That was really helpful. Thank you!

Answer 2

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.