0
$\begingroup$

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!

$\endgroup$
  • $\begingroup$ I'd start by wondering if a configuration can occur exactly twice, or exactly $N$ times. $\endgroup$ – chi Jan 22 '18 at 9:43
  • $\begingroup$ @chi If a configuration occur more then once, than it will occur infinite times since we entered a loop. But how does it help? A machine can never halt without repeating a configuration. $\endgroup$ – Mickey Jan 22 '18 at 15:52
  • 1
    $\begingroup$ Indeed! So "repeats a configuration infinite times" can be simplified to "repeats a configuration at least twice". Can you recognize that? $\endgroup$ – chi Jan 22 '18 at 16:53
  • $\begingroup$ @chi Yes, it is actually pretty simple for the case that there is one word that repeats a configuration, don't know how I have missed that. The solution for L_2 was given by Ariel, thanks. $\endgroup$ – Mickey Jan 23 '18 at 10:04
2
$\begingroup$

$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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.