formal-languages - P 不可判定且不可半可判定，Q 不可判定且可半可判定且 P ⊂ Q

Question

我的问题：定义两个单词集合 P 和 Q（即两个问题）使得：P 不可判定且不可半可判定，Q 不可判定且可半可判定且 P ⊂ Q

Answer 1

此类集合的一个示例：

将 Q 定义为一组图灵机，在空输入时停止。将 P 定义为一组图灵机，在每个输入时都停止。

显然 P ⊂ Q 和 P 是不可判定且不可半可判定的，而 Q 是不可判定且半可判定的。