質問

Say $ \Sigma = \{a\} $, $M_1, M_2, ... $ is an enumeration of all TMs that recognize languages over $\Sigma$ and $L_1, L_2, ... $ are respectively the languages that are recognized by those TMs. We construct the language $ L = \{ a^n\ |\ a^n \not\in L_n \} $. Is $L$ Turing recognizable (recursively enumerable)?

My thought process is this: Say $L$ is recognizable. Then given a string $a^k$, we find $L_k$ based on the enumeration of $L_i$'s, and then we run $M_k$ on input $a^k$ to find if indeed $a^k \not\in L_k$. We must accept if $a^k \not\in L_k$, but $M_k$ is not guaranteed to halt in that case. So $L$ is not recognizable.

Now I have 2 questions: 1) Is my thought correct?, and 2) How can I make this more formal?

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

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