Decidability Vs Semi-Decidability Vs Undecidability Self Doubt

Question

Please tell whether the following is Decidable, Semi-decidable or Undecidable

1. A turing machine halts after running for exactly k steps

2. A turing machine halts after running for atmost k steps

3. A turing machine halts after running for atleast k steps

4. A turing machine accepts a string "x" after running for exactly k steps

5. A turing machine accepts a string "x" after running for atmost k steps

6. A turing machine accepts a string "x" after running for atleast k steps

7. A turing machine visits a particular state "q" exactly k times

8. A turing machine visits a particular state "q" atmost k times

9. A turing machine visits a particular state "q" atleast k times

10. A turing machine visits a particular state "q" exactly k times on input "x"

11. A turing machine visits a particular state "q" atmost k times on input "x"

12. A turing machine visits a particular state "q" atleast k times on input "x"

Comments

1. D

2. D

3. UD

4. D

5. D

6,7,8,9,10,11,12 : UD

---

Deepakk Poonia (Dee)  3 is UD because we don't know whether the TM after running for k steps will actually halt or not in the future?

And for 1 and 2..we don't have to check for all the inputs right? Can you please share your approach for all the statements? I face problems in these..one of the ways that i have seen is separating all the strings of length=k and run them on TM. If all of them take exactly k steps then we can say that other strings(length>k) having their substrings in the 1st partition will also take exactly k steps.. if this is so i have doubts...

Thanks in advance :)

---

Check the complete answer.