算法分析导论：图灵机、有效计算和计算模型

算法分析导论 在这篇讲义中，我们将探讨算法分析的基础知识，特别是图灵机的概念和历史背景。 **图灵机** 图灵机（Turing Machine，TM）是一种抽象的计算模型，由Alan Turing在1936年发明。图灵机可以计算任何通常被认为是可计算的函数；事实上，将可计算定义为图灵机可计算是相当合理的。图灵机的出现早于真正的计算机，dating back to the 1930s when mathematicians were trying to understand the concept of "effective computation". **有效计算** 在20世纪30年代，数学家们尝试定义“有效计算”的概念以区分可计算和不可计算的问题。他们知道各种有效计算的算法，但他们不太确定如何以一种普遍的方式定义“有效计算”。为了确定这个概念，出现了几种不同的形式化方法，每种方法都有其自己的特点： * 图灵机（艾伦·图灵） * Post系统（埃米尔·波斯特） * µ-递归函数（库尔特·哥德尔，雅克·埃尔布朗） * λ-演算（阿隆佐·邱奇，斯蒂芬·克利尼） * 组合逻辑（莫西斯·舒恩菲克尔，哈斯克尔·柯里） 所有这些系统都体现了一种或另一种形式的有效计算的思想。它们处理各种类型的数据；例如，图灵机操作有限字母表上的字符串，µ-递归函数操作自然数，λ-演算操作λ-项，组合逻辑操作由组合符号构建的项。 **数据表示** 所有这些不同类型的数据之间存在自然的转换。例如，让{0,1}∗表示字母表{0,1}上所有有限长度的字符串的集合。存在一个简单的一一对应关系{0,1}∗和自然数N={0,1,2,}之间，定义如下： x → #(1x)−1, 其中#y是由二进制字符串y表示的自然数。相反地，将几乎任何东西（自然数、λ-项、{0,1,2,,9}∗中的字符串、树、图等）编码为{0,1}∗中的字符串是很容易的。在这些数据的自然编码下，所有上述形式主义都可以模拟彼此，因此尽管它们在表面上有所不同，但它们在计算上是等价的。 **现代计算机** 如今，我们可以毫不掩饰地利用我们更现代的视角，并将编程语言如Java或C（或它们的理想化版本）添加到这个列表中-与Church和G¨odel所必须努力应对的情况相比，这是一种真正的奢侈。在上面列出的经典系统中，最接近现代计算机的是图灵机。除了我们将在下面定义的现成模型外，还有许多定制变体（非-确定性、多带、多维带、双向无限带等），它们在计算上等效，即它们都可以相互模拟。