Dan*_*ing 4 state-machine turing-machines computation-theory
在进行考试修订时,我无法回答Sipser所着的"计算理论导论"一书中的以下问题.不幸的是,书中没有解决这个问题的方法.
解释为什么以下不是合法的图灵机.
M = {
输入是变量x1,...,xn上的多项式p
这真让我抓狂!我怀疑是因为整数集是无限的？这是否超出了字母表允许的大小？
小智 6
虽然这是描述图灵机的一种非正式方式,但我会说问题是以下之一:
otherwise reject - 我同意Welbog的意见.由于你有一套可能无限的可能设置,机器永远无法知道它的评估结果是否仍然存在,如果没有找到任何设置,它将永远循环 - 只有遇到这样的设置时,机器可能会停止.最后一个语句是无用的,永远不会成立,除非你将机器限制为一组有限的整数.
代码顺序:我会把这个伪代码读作"首先写下所有可能的设置,然后评估每个可能的设置",这就是你的问题:再次,通过拥有一组无限可能的设置,甚至第一部分都不会终止,因为永远不会有最后一个设置写下来并继续下一步.在这种情况下,机器甚至不能说"没有0设置",但它甚至不能开始评估找到一个.这也可以通过限制整数集来解决.
无论如何,我不认为问题是字母表的大小.您不会使用无限字母表,因为您的整数可以用十进制/二进制/等编写,而那些只使用(非常)有限字母表.