hzx:任意给定计算机,我可以构造等价的DFA。
斌头:好,我给一台计算机给你,存储空间8bits,每个bit有两种状态,你要构造有多少个状态的DFA?
hzx:我只需要最多
斌头:那我这台计算机刚好有
hzx:那我就构造
斌头:不好意思,数错了,是
hzx:没关系,你有多少状态我就构造多少个状态出来给你。
斌头:数不清怎么办?
hzx:没关系,总归是有限状态,不然你叫什么有限状态图灵机?
请问,最后谁会赢得这次构造游戏?
我相信我会赢。因为确实,计算机的状态没人数得出来,否则就不会存在“停机问题”了。