Does the language of TM's that repeat a configuration infinite times semi-decidable or not?

Question

Let us define the following languages: _{$$ {L_1 = \{\langle M\rangle : M \ \text{is a TM and $\exists w\in \Sigma^*$ s.t $M(w)$ repeats a configuration infinite times}\}} $$}

_{$$ L_2 = \{\langle M\rangle : M \ \text{is a TM and on all inputs there exists a configuration that repeats infinite times}\} $$}

My question is what class does this languages belong to ($\mathcal{R},\mathcal{RE\setminus{R}}, etc...$)? I have shown that:

${H_{TM}}\le_m L_2$: On input $\langle M,w\rangle$ return a new $TM$ $\langle M' \rangle$ such that on all inputs, runs $M$ on $w$. Keep a counter at the beginning on the number of steps (to avoid entering the same configuration infinite number of times, if it doesn't stop). If it does stop, repeat some configuration in a loop.

So that seem to prove that $L_1,L_2\notin \mathcal{R},\mathcal{co-RE}$.

But is it in $\mathcal{RE}$? I couldn't write a $TM$ that accepts those languages, nor derive a reduction from $\overline{H_{TM}}$, $\overline{A_{TM}}$ or any other relevant language.

Any ideas on solving this? Thanks!

Answer 1

$L_1$ is indeed recursively enumerable. Suppose for simplicity that the input consists of a pair $M,w$ and you want to know whether $M$ repeats a configuration during its computation on $w$. You can then loop over the integers, and for each $n\in\mathbb{N}$ check if $M$ repeats a configuration with input $w$ during the first $n$ steps. This is possible since during the first $n$ steps $M$ uses at most $n$ cells from the tape, hence the number of possible configurations is finite (you can store them in memory and mark those which were seen).

Now, you want to add an additional existential quantifier over the words $w$, and this can be achieved by dovetailing. Simultaneously scan words and computations length, i.e. for each $n$ and for all words of length $\le n$, check if $M$ repeats a configuration during its first $n$ steps.

The additional universal quantifier prevents $L_2$ from being recursively enumerable, you can show this by reduction from the complement of the halting problem. Given $(M,w)$, your reduction outputs a machine which on input $x$ simulates $M$ on $w$ for $|x|$ steps, and enters a loop iff $M$ did not halt in this time.