オートマチックチューリング

Question

誰かが段階的に質問を説明できますか？

Σは有限集合であり、L1、L2及びL3は、以下の特性満足Σ^ *の許容されるサブセットチューリングされていることを仮定する： L1∪L2∪L3 =Σ^ * と、 L1∩L2 = L2∩L3 = L3∩L1 =∅である。 L1、L2、L3はすべて再帰的でなければならないことを示します。

Answer 1

我々は、その与えられている：

L1 union L2 union L3 = E* 
L1 intersect L2 = {} 
L1 intersect L3 = {} 
L2 intersect L3 = {} 
L1 is acceptable/semidecidable/recursively enumerable/recognizable 
L2 is acceptable/semidecidable/recursively enumerable/recognizable 
L3 is acceptable/semidecidable/recursively enumerable/recognizable 

我々は、L1、L2およびL3を共認識/再帰/決定可能/不合格であることを示す必要があります。

文字列がL1にないことを示すことはできますか？はい。これら3つの言語の和集合にはすべての文字列が含まれているため、2つの言語が重複しないため、L1にない文字列はL2またはL3のいずれかになります。これらの言語は受け入れ可能/半割り可能/再帰的に列挙可能/認識可能であるため、最終的にL2とL3の文字列を受け入れる/決定する/列挙する/認識するTMs TM2とTM3があります。文字列がL1にないことを認識するために、T2とT3を実行し、いずれかが文字列を受け入れる/決定する/列挙する/認識するかどうかを調べることができます。

L1は、許容可能/再帰的に列挙可能/認識可能であり、同時に、拒絶可能であること/共回帰的に列挙可能/共認識可能であることが分かっている。このような言語は決定可能/再帰的です。

L1、L2、およびL3には任意に番号が付けられているため、L1に適用される結果は、L2およびL3にも適用する必要があります。言い換えれば、L2とL3のどちらかでL1を交換すると、上記とまったく同じ引数が適用されます。

したがって、3つの言語のそれぞれは、決定可能/再帰的です。