computation-theory - 如何证明一个集合是可判定的、半可判定的或不可半可判定的？

Question

我被要求证明以下集合是可判定的、半可判定的还是非半可判定的：

换句话说，它是一组输入，使得存在一个用自然 y 和输入 p 编码的图灵机返回其输入。

将集合 K 视为自然集合，使得用 x 和输入 x 编码的图灵机停止。这被证明是一个不可判定的集合。

我认为我需要的是找到 K 到 L 的约简，但我不知道如何证明 L 是可判定的、半可判定的或不可半可判定的。

Answer 1

乍一看，L 可能看起来不可判定，因为包含了这个讨厌的无界量词，当您寻找满足特定 p 条件的 a 时，这似乎使得可能无限搜索成为必要。

然而，答案要简单得多：有一个图灵机 M 总是返回其输入，即 M(p) = p 适用于所考虑语言中的所有p。假设 y 是 M 的代码。那么你可以对所有 p 使用相同的 y，表明 L 包含该语言的所有单词。因此L当然是可判定的。

事实上，这是一个展示外延性原理的例子（如果两个集合具有相同的元素并且一个是可判定的，那么另一个也是可判定的，即使看起来不是这样）。