我有以下我不完全理解的证明。
L D /是对角线化语言的补充。
L U是通用语言。
假设U *是Lu的TM，它总是停止。为L D /设计一个TM D / *。将输入x = wi提供给TM R，TM R计算索引i和第i个TM Mi，并输出单词y = Code（Mi）111wi。然后，可以将y用作U *的有效输入。 U *仅在Mi接受wi时接受。如果x = wi在L D /中，情况就是这样。我们得到等价x表示为L D / y表示为LU。因此，D / *决定L D /，这是一个矛盾，因为我们知道L D /不是递归的，因此L U也不是。
通过对角化语言的补充，通过减少证明通用语言不是递归的
•
问答
tldtc007 回答：通过对角化语言的补充，通过减少证明通用语言不是递归的
暂时没有好的解决方案，如果你有好的解决方案，请发邮件至：iooj@foxmail.com