質問

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!

正しい解決策はありません

ライセンス: CC-BY-SA帰属
所属していません cs.stackexchange
scroll top