input: <M> (M is a TM)
Question: Does there exists an input y such that while M runs on y, it goes threw a prime number of states. (If it passes on the same state more then once, we count the state just once).
Solution: the problem isn't in Re nor in coRE.
I thought i had an algorithm which proves that this problem is in RE:
In the kth step, run words 1…k (lexicographly ordered) on M. For each word, count (on a second tape) the number of states used (or mark all the used states. for each word in each step, clear the second tape before the simulation. If at any point M halts, count the states marked on tape 2 and check is this number is prime. If so - accept. If no, carry on.
Why is this wrong?