Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
    
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

2 Answers 2

up vote 5 down vote accepted

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

share|improve this answer
    
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$.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.