与相关同学讨论过很多次,互相都无法说服对方。我尝试再做努力。
目前讨论双方达成的共识就是,说“有限存储图灵机等价于DFA”的理由是:有限存储TM的状态有限,既然有限,则可枚举,利用枚举出的所有状态,必可构造相应的DFA。
首先,“有限存储”这个限定其实是不必须的,因为,即使是无限存储的TM,其状态也可能是有限。根据上文,只要状态有限,则可构造DFA。所以,某些无限存储TM也可等价于DFA。我强调这一点,主要是认为我们的讨论不应该重点放在“有限存储”上,而是“等价”。
什么是等价,就是你能做的事情,我也能做。试想这样一种情形,我是TM一方,记为A,对方记为B。A说:我能做整数加法,你DFA能做吗?B:能,只要是有限的加法,你能做我就能做。A:好,那请你构造好机器,你构造好了,我就告诉你题目,而且我一定确保是有限计算。B:不行,你是有限机器,你必须告诉我你有多少比特,或者比特上限。请问,这里是分歧所在吗?
即使是告诉你一个上限,比如,现在的计算机有12G的存储空间。于是,再次展开竞赛。A:我有12G存储,你准备好了吗?B:没问题,这次做什么?A:还是做加法,这次就算
如果上面还不能说服你们,那再考虑一种情形。假如存在一台可以求解哥德巴赫猜想的GB-TM,当然,这样的东西还没被发明。A:很高兴,我发现了GB-TM,它可以求解哥德巴赫猜想。B:是吗?你这台机器是有限TM?A:是的,存储器只有1024M比特。B:哈哈,那我这里有一台DFA与它等价。A:真的吗?你构造出来了吗?B:不用,显然存在,根本不需要讨论。A:太好了,你告诉我答案吧,是真还是假?B:你说是真就是真,你说是假就是假,你告诉我答案先。A:不是,你不是跟我等价吗?为什么要我告诉你答案?B:你都没答案,我怎么构造?
这就是我为什么不认同“有限存储图灵机等价于DFA”,把某台TM的状态记录下来能称为”等价“吗?
课本确实说了,DFA等价于某些计算机。当然,一台识别正则语言的计算机当然会有DFA与之等价了。而且,下这个结论都是针对双方可以解决的问题而言。DFA离开其所能识别的语言去谈状态,不可取。DFA不应该是状态记录器。
如果,到此我们双方依然没办法说服对方。没关系!但是,我呼吁,对问题的讨论,不可情绪化,应该回归到问题本身。讨论问题是为了理清思路,帮助思考,寻求更多的发展。同时还需要一种包容的心态,一种开放的态度。过早地先下结论,封闭自我,没什么帮助。
总之,说了这么多,我依然相信,这个问题有值得讨论的地方,我会保持开放的心态接受更多的反面意见。如果有同学可以从DFA定义本身出发提出自己的观点,更好!我认为,这恰好是我讨论中缺乏的东西。