0
$\begingroup$

I'm trying to use reduction $\overline{HP} \leq L$, but I just can't think of a way to do so.
Any help would be appreciated!

$\endgroup$
2
  • 1
    $\begingroup$ "Is that a TM not in RE?" makes absolutely no sense. $\endgroup$
    – Arno
    Feb 21 at 11:49
  • $\begingroup$ I could have guessed, but using confused language just makes it much harder for you to actually figure stuff out. $\endgroup$
    – Arno
    Feb 21 at 12:06

3 Answers 3

1
$\begingroup$

The machine would go in an infinite loop if there is at least one state that it visits an infinite number of times (By pigeon-hole principle).

Hint: Dovetailing

$\endgroup$
0
$\begingroup$

Hint: given a Turing machine $M$ and a word $w$ over $M$'s alphabet, consider a machine $T$, that on the empty word simulates the run of $M$ on $w$. Can you force $T$ to visit a state infinitly often if the simulation does not halt? Note that ofcourse there is such a state but we do not know it in advacnce to output it in the reduction, but there is a simple way around this: you can modify the simulation anyway you see fit.

$\endgroup$
0
$\begingroup$

I got it.
Using reduction $\overline{HP} \leq L$ with $f\left ( \left ( \left \langle M \right \rangle ,x \right ) \right ) = \left ( \left \langle M_x \right \rangle ,q\right )$ where $M_x$ is a TM which simulates M on input x, but between every two steps, it goes into state q. If $M_x$ halts, reject.
This means that if $\left ( \left \langle M \right \rangle ,x \right ) \in \overline{HP}$ then M does not halt on x, which means $M$ will be in an infinite loop which means $M_x$ will visit state q infinite times.
If $\left ( \left \langle M \right \rangle ,x \right ) \notin \overline{HP}$ then $M$ will halt which means $M_x$ visits q $n \in \mathbb{N}$ times.

$\endgroup$
1
  • 2
    $\begingroup$ Correct, but I encourage you to write it more clearly. (1) $M_x$, on input $y$, ignores $y$ and then simulates the run of $M$ on $x$. (2) Some people use "loop" to indicate a state visited infinitely often, but the use of "loop" usually means a loop of configurations. If you meant a loop of states, you should write that explicitly: "a loop of states". (3) "it goes into a state $q$, where $q$ a is special state of $M_x$". $\endgroup$ Feb 21 at 14:53

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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