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!

No correct solution

Licensed under: CC-BY-SA with attribution
Not affiliated with cs.stackexchange
scroll top