如何通过图灵机解释“邱奇-图灵论题”
——Forouzan的《计算机科学导论》笔记(一)

Forouzan著的《计算机科学导论》第十七章中,为了说明“邱奇-图灵论题”,作者介绍了一种只有“递增、递减和循环”三条语句的简单编程语言,指出任何一种实际的高级编程语言都可以用这种简单语言模拟;然后作者介绍了图灵机的概念,并详细解释了如何用图灵机来模拟这种简单语言;在此基础上,作者发问“图灵机是否能解决一台计算能解决的任何问题?”,从而提出了邱奇-图灵论题。作者的思维脉络十分清晰,但我在学习的时候有个问题很困惑。

困惑之处:三条语句使用三台图灵机来模拟

作者对三条语句设计了三台不同图灵机,递增语句的图灵机有四种状态,递减语句的图灵机有三种状态,循环语句的图灵机则有至少七种状态。计算机在实际复杂的解决问题时,肯定不是单一的递增、递减、循环语句就能胜任的,这三条语句肯定会同时被用到。让我困惑的地方就在于这儿,总不能把待解决的问题拆分开来,让三台不同的图灵机分别去执行吧?对于一个复杂的问题,是否存在一台整合了三条语句的图灵机来解决它?直觉告诉我应该是这样的。

我的思考

我感觉线索应该在于循环语句中。循环语句的循环体中,可以包括任意多的递增、递减语句,甚至循环语句自身。在循环语句的图灵机中,状态BS代表了循环体的开始状态,状态BH定义了循环体的结束状态,在这两个状态之间,我感觉应该存在更多状态,这些状态对应于循环体中包含的语句被执行时状态。这样一来,通过循环语句可以整合一切复杂逻辑,只需一台图灵机而不是三台,就可以完成这些逻辑;这台图灵机可能因为问题的复杂度较高,而具有很多状态,但这些状态是有限的。

我的困惑似乎解决了。不知道各位读者是什么看法呢?下图是原书中循环语句的图灵机示意图(里面有拼写错误):

while循环语句的图灵机模拟

吐槽一下翻译

Forouzan的这本《计算机科学导论》,充分体现了“导论”的特点,内容全面但并不是蜻蜓点水,而且没有过多形式化的晦涩语言,很适合我这样的非科班计算机从业人员。但是这本书的翻译实在太糟糕了,里面有一些错误(比如本文的插图)姑且不说,最要命的很多翻译后的句子文理不通,形同天书。比如303页在解释while循环语句的图灵机时,有如下语句:

状态MR把读/写头移过在每次重复中在处理数据开始时定义了数据开始位置的空白符号;状态ML把读写头移过在每次重复中在处理数据结束时定义了X的开始位置的空白符号。

这两句话我读了好几遍还是没能成功断句,更不用提理解了,太可怕了。如果不是因为本书有配图,这个地方绝对不能让我理解循环语句的图灵机模型。