formal-languages - P は決定不能かつ半決定不能、Q は決定不能かつ半決定可能、P ⊂ Q

Question

私の問題: 単語の 2 つのセット P と Q (つまり、2 つの問題) を次のように定義します。

Answer 1

そのようなセットの一例:

空の入力で停止するチューリング マシンのセットとして Q を定義します。入力ごとに停止するチューリング マシンのセットとして P を定義します。

明らかに P ⊂ Q であり、P は決定不能かつ半決定可能ではありませんが、Q は決定不能かつ半決定可能です。