L is defined as the following language :
{ $<M>$ | M is a TM and for all input w, in the computation M(w) there is a state q that is visited an infinite number of times }
I was asked to prove that the language is not recursive enumerable yet I can't seem to get the reduction right. Any help/clues or hints will be gladly accepted. Thanks!
The language above defines the set of Turing machines which never halt on any input. Note, this is the same thing as visiting a state an infinite number of times, assuming that the number of states are finite- apply an infinite version of the pigeon hole principle.
So, if this language was recusively enumerable, there'd be a Turing machine to decide whether each of its members belonged or not. So we'd be able to compute whether a machine never halted on any input. But this is impossible, because then we'd be able to solve the halting problem. I'll explain why in the next paragraph.
The assumption is we have a machine that can decide when another machine never halts on any input. Now we want to build a machine that solves the halting problem: for any $M$ and $x$, we want to decided whether $M(x)$ halts. Well, we can easily define a computer $C$ which ignores its input and just runs $M(x)$ every time $C(y) = M(x)$. Now we know that $C(y)$, because it ignores its input, either always halts for all inputs $y$ or never halts for any of them. But by our assumption we have a machine that decides whether $C$ never halts. The answer we get from this will give us the answer to $M(x)$ and solve the halting problem.