Does $L=\{(\langle M \rangle,k)| M$ is a TM and $\exists w\in \sum^*$ s.t when $M$ runs on $w$, $M$ visits some state at least $k$ times$\} \in R$?

Question

I'd like your help with understanding , how come the following language is decidable (in $R$):

$L=\{(\langle M \rangle,k)| M$ is a TM and $\exists w\in \sum^*$ such that when $M$ runs on $w$, $M$ visits some state at least $k$ times$\}$

I tried to think of a Turing machine which decides the problem, but I didn't reach to any smart conclusions.

Answer 1

The language is really in $R$. To see if a TM with $N$ states visits one of them at least $k$ times you only need to check $N \cdot k$ steps of it. In $N \cdot k$ steps, only $N \cdot k$ symbols can be used and thus only words $N \cdot k$ symbols long need to be considered. There is only a finite number of such words. In the end the time needed to check if TM belongs in L is $|\Sigma|^{N \cdot k}N \cdot k$.

Answer 2

If $M$ has $n$ states, then after $nk$ steps it will either have stopped or visited some state at least $k$ times. $nk$ steps doesn't leave the machine time to read more than the first $nk$ symbols of its input, so you can decide $L$ in finite time by simulating $M$ for up to $nk$ steps on each possible input tape of length $nk$.