クリーネスター決定不能

Question

私はトラブルこれを解決持っていますLが決定可能であるならば、我々はそのL *はまた、チューリングマシンを構築することにより決定可能であることを証明できることを知っているが、 ：Lが決定不能である場合には、L *はまた、決定不能である を。 この文は真か偽ですか？

Answer 1

これは誤りです。 Lを決めることのできない言葉にする。 Rに長さ1のすべての文字列が追加された状態でLを定義します（まだLに含まれていない場合）。 Rにはアルファベットの長さ1のすべての文字列が定義されています。また、Lは決めることができないので、Rでなければなりません（決めることができない言語と有限の言語の和集合も決めることができません;以下のコメントを参照してください）。しかしR *には、アルファベットのすべての文字列、決定的な言葉が含まれています（実際、それは規則的です）。明確にするために、われわれはちょうど、決めることのできない言語から、その主張の反例である別のものを構築する方法を示した。

決めることができない言語と有限言語の和集合が決めることができないことを知るためには、Lが決定不能であり、Rが有限である場合、Lの組合Rは決定可能であると仮定する。つまり、L組合Rのメンバーシップを決めるTMがあります.Rが交差するRを決めるTMがあることはわかります.Rが有限であれば、それ以外のものとの交差もそうです。しかし、L =（（L組合R）setminus R）組合（L Rと交差する）：RはLのすべてまたはR

setminus RはR

に

ではありませんLのすべてである

1. L組合組合（L intersect R）はすべてLである。

決定可能な言語は集合差と組合によって閉じられるので、Lは決定可能でなければならず、矛盾でなければならない。だからL組合Rは決めることができないLと有限Rのために決めることができません。