证明输入x}的语言L= {w∈{0，1}∗Mw(x)↓是部分可判定但不可判定的

Question

我试图证明输入x}的语言L= {w∈{0，1}∗Mw(x)↓是部分可判定的，但不是可判定的。Mw是M的编码，因此L语言使机器M的所有编码在某个输入x上停止。

我有两个想法：

1. 将其简化为使用某些判定器TM的停止问题。
2. 利用Post定理，以某种方式证明了L的补是不可判定的，但L是部分可判定的

但是，我很难决定这两种方法中哪一种实际上是正确的，以及如何用正确的符号来写它。有人能给点提示吗？

Answer 1

这个答案假设L是图灵机器的所有表示语言，这些机器在某些输入上停顿。

首先，这种语言必须是半可判定的，或者是递归枚举的，因为我们可以枚举停止某些输入的图灵机编码。为此，请开始枚举所有二进制字符串。在每个阶段，开始一个新的TM，它开始模拟在所有可能的输入上生成的字符串编码的机器的执行。继续进行，以便在所有可能的输入上模拟所有可能的TM编码。配合这些机器的执行，使每个机器在有限的时间内得到其下一个时间量子，以便在有限的时间内在每一个可能的TM上模拟每个可能的输入。如果任何一个模拟停止，那么我们打印出在输入上停止的编码，我们可以停止模拟该编码。这最终必须打印出语言中的任何编码，以便枚举语言。这意味着我们可以回答这个问题，“这个TM在语言中吗？”对于任何提供的TM，考虑到答案是肯定的(因为我们最终会遇到它)。

第二，语言不能被判定，或者是递归的，因为这给了我们一种明确的方法来决定停止问题:询问在语言中有问题的TM是否在语言中，并得到一个“是”或“否”的答案，说明它是否停止了某些输入。我们总是可以修改感兴趣的TM，这样它只能在任何感兴趣的输入上停止，然后如果我们有一个特定的输入，就将它输入到我们的决策器中。

第三，这些事实意味着语言不是共递归可枚举的，因为它既是递归枚举的，也是共递归枚举的，这意味着它是递归的，事实并非如此。