The Question:

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.

My problem:

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?

thanks