交差点が決定可能な抱えていない問題の例

Question

私は、2つの問題が判断不可能であることを考えると、彼らの交差点が決定不可能であるに違いないことは従わないことを知っています。たとえば、言語$ p $のプロパティを取得して、特定のプッシュダウンオートマトン$ m $によって受け入れられた言語がそのプロパティを持っているかどうかは把握できません。明らかに$ p $と$ lnot p $は把握できません（与えられた$ m $の場合）が、$ p cap lnot p $は簡単に決定できます（常に偽です）。

上記の「トリック」を利用しない「現実の」例があるのだろうか？私が「現実の生活」と言うとき、私は必ずしも人々が日々の生活で出会う問題を意味するわけではありません。交差点が簡単に決定できない例がある場合、それは（私にとって）興味深いでしょう。

Answer 1

だからここに例があります、それはおそらくそうではありません 良い あなたが望んでいたように、しかしあなたが言及したものよりも些細なことは少ない。

$ l_1、l_2 subset {a、b、c }^*$は、2つの決定不可能な言語と、$ l_3 subseteq {a、b、c }^*$ dicidable言語とします。定義します

begin {align} l_a＆：= {a 、w mid w in l_1 } cup {c 、w mid w in l_3 }、 l_b＆：= {b 、w mid w in l_2 } cup {c 、w in w in l_3 }。 end {align}

明らかに、$ l_a $と$ l_b $の両方は決定できませんが、それらの非空白の交差点$$ l_a cap l_b = {c 、w in l_3 } $$は決定できます。