哪種不確定的語言$ B $可以還原為它的補語?


0

我遇到了一個問題,要求給出一個不確定語言的示例 $ B $ 這樣的 $ B \ leq_m\ overline {B} $ ...

但是,我發現很難構造一個示例...我的困難是,鑑於一種不確定但圖靈可識別的語言,請說 $ A_ {TM} $ ,其補語 $ \ overline {A_ {TM}} $ 無法識別圖靈並循環播放。如果我簡化這種語言(例如 $ x \ in A_ {TM} \ leq_m y \ in \ overline {A_ {TM}} $ ,則實例 $ y \ in \ overline {A_ {TM}} $ 無法被任何TM識別(由於定義, $ \ overline {A_{TM}} $ 正在循環)...

有幫助嗎?

3

Let $H$ be the language of all Turing machines that halt on empty input. Clearly $H$ is undecidable.

Let $L = \{ (1,T) : T \in H \} \cup \{ (0,T) : T \not\in H \}$.

Clearly $L$ is undecidable. If $L$ were decidable, then a Turing machine $M$ for $L$ would also imply the existence of a Turing machine $M'$ that decides $H$. $M'$ with input $T$ simply simulates $M$ with input $(1,T)$.

Moreover, for a Turing machine $T$ and $x \in \{0,1\}$ we have: $$ (x, T) \in L \iff (1-x, T) \not\in L \iff (1-x, T) \in \overline{L}. $$

This, combined with the fact that we can decide whether a given word encodes a valid Turing machine, shows that $L$ is reducible to $\overline{L}$.