質問

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?

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

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