edited by
2,394 views
9 votes
9 votes

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"

edited by

Please log in or register to answer this question.

Related questions