### 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.