# 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$?

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.

-
The language is clearly recursively enumerable. I somehow doubt it is decidable though. –  Karolis Juodelė Aug 5 '12 at 13:07
Well I thought it as well, but apparently from the answers of this multi-choice question, it says that it is in $R$.. –  Jozef Aug 5 '12 at 13:10

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

-
Thank you for the answer. you both have quiet the same answer, so since Henning was one minute ahead you, I accepted his answer. I hope you don't mind :) –  Jozef Aug 5 '12 at 14:10
@Jozef: Actually I was 13 seconds late. –  Henning Makholm Aug 5 '12 at 14:15
Ok Fixed :).... –  Jozef Aug 5 '12 at 14:19

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

-