1. A turing machine halts after running for exactly k steps
2. A turing machine halts after running for atmost 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
These are informal statements. So, before answering them, let me make them formal as they should have been asked.
$L=$ $\left \{ ⟨M⟩|M\,\, is\,\, a\,\, TM\,\, which\,\, halts\,\, for\,\, every\,\, input \,\,in\,\, at\,\, most \,\,K \,\,steps \,\,for\,\, some\,\, K \geq 1 \right \}$
It is Decidable. Because if the machine $M$ halts after at most $K$ steps, then only the cells $0,1,…,K−1$ on the tape are significant. Then it suffices to simulate the machine $M$ on all input strings of the form $x∈Σ^K$, of which there are a finite number.
- If any of these simulations fail to enter a halting state by the $K^{th}$ transition, this indicates that any input string starting with $x$ is one for which the machine does not stop within the first $K$ steps.
- If all of these simulations halt by the $K^{th}$ transition, then $M$ halts within $K$ steps on all inputs of any length (of which the substring of length $K$ is all that it ever acts on).
NOTE that similar logic can be applied for any of the following combinations :
$\left \{ For \,\,all\,\, strings, For \,\,some \,\,string, for\,\, no \,\,string, \,\,for\,\, the\,\, given\,\, string \right \} \times \left \{ at\,\, most\,\, K\,\, steps, exactly \,\,K\,\, steps, exactly\,\, after\,\, K\,\, steps \right \}$
Every such pair will be Decidable by the similar logic as above explained.
3. A turing machine halts after running for atleast k steps
6. A turing machine accepts a string "x" after running for atleast k steps
It is Undecidable as We can easily see that If it were Decidable then Halting Problem would also be Decidable. Put $K = 1$ and this problem is nothing but the standard Halting Problem of TM.
We know that "whether or not a Turing machine will reach the Halt state for some initial tape" is known as the Halting Problem. i.e. It asks, "given a computer program and an input, will the program terminate or will it run forever? " is halting Problem and It is Undecidable.
For Problem statements $7 \,\,to\,\,12$, First let's see the following Problem :
$L =$ {$⟨M,q,x⟩| M\,\, is\,\, a\,\, Turing\,\, machine\,\, and \,\,q \,\,is\,\, a\,\, particular \,\,state\,\, of\,\, M\,\, and \,\,running\,\, of\,\, M\,\, on\,\, w\,\, visits\,\, q$}
Moreover, It is one of the Standard Undecidable Problems and also known as State Entry Problem. It is Undecidable Because if you can decide if $⟨M,q,x⟩$ is in your language, then you can decide if the machine $M$ stops on input $x$, by testing if $⟨M,h,x⟩$ is in your language ($h$ is the halting state). So you can decide the halting problem. And this problem is undecidable, so is the language $L$.
Problem Statements $7 \,\,to\,\,12$ are all Undecidable as we can see. Just Put $K = 1$ and all those statements will become State Entry Problem Statements.