Recognizably turing machine question (reject / loop)
-
05-11-2019 - |
Question
The definition of proving recognizability using dove tailing is below. However I'm wondering if we can also prove loop or reject in the same way?
Give a deterministic TM D that recognizes L such that if $w \in L$ then D accepts w. Or if $w \notin L$, then D does not accept $w$. I realized this definition states on whether D accepts a $w$ like
$A_{*111} = \{\langle M \rangle \mid M$ is a TM, and $M$ accepts some string that ends with 111$\}$, which is recognizable and easy to prove through dovetailing.
Now how about
$R_{*111} = \{\langle M \rangle \mid M$ is a TM, and $M$ reject some string that ends with 111$\}$? Is this also recognizable and would the proof be the same as the one above ? I think this will work but what about
$L_{*111} = \{\langle M \rangle \mid M$ is a TM, and $M$ loops on some string that ends with 111$\}$?
How do you check if something loops?
No correct solution