-
-
没有人
对于这个问题,@bintou 的答案也没错,只是我还是无法convince myself。经过一番搜索,发现也有人提出一样的问题。
答案的意思是说被simulate的机器必须可被编码,这和我上一年的答案是一样的,然而,仔细一想,DFA那些肯定也是可以编码的啊!今天再想了一下,发现没错,就是能力的问题,而且我想到一个更加严谨的证明方法(这里以DFA为例):
因为DFA可编码,所以对于被编码为的DFA,存在可计算函数 与其对应
设
则不可能是DFA,因为任意对 都有
但是,若DFA的simulator可以是DFA,则肯定可以被计算,因为计算 只需simulate一个DFA,对最终结果加1即可。
从而,DFA的simulator不可能是DFA。
对于上述证明过程,欢迎大家指出不足。 -
没有人
我的理解是这样的:
recognizes language if . 因此,
是包含于 的定义域的。并不是@hzx__ 说的“只能接受”。
(话说。。。这里的LaTex公式怎么不能显示花括号???) -
没有人
详见ITOC中定理4.11的证明,在该证明过程中,似乎可以把“M is a TM”换成任意其他机器,如"M is a NFA",替换之后仍然可以推导出最终的矛盾,从而证明该
机器对应的 是undecidable的。显然这推广出来的结论是不对的,为什么?为什么就只有图灵机是可以这么证明的? -
-
-
-