心智计算理论 (2015)

计算和算法的直观概念是数学的核心。粗略地说，算法是用于回答某些问题或解决某些问题的明确的、逐步的过程。算法提供常规机械指令，指示如何进行每个步骤。遵守指示不需要特殊的聪明才智或创造力。例如，熟悉的小学算法描述了如何计算加法、乘法和除法。直到二十世纪初，数学家都依赖于计算和算法的非正式概念，而没有尝试任何形式分析之类的东西。数学基础的发展最终促使逻辑学家寻求更系统的处理。艾伦·图灵 (Alan Turing) 的里程碑式论文“论可计算数，及其在解决问题中的应用”（图灵，1936 年）提供了被证明最具影响力的分析。图灵机是理想化计算设备的抽象模型，具有无限的时间和存储空间可供使用。该设备操纵符号，就像人类计算代理在算术计算期间操纵纸上的铅笔标记一样。图灵很少谈到符号的本质。他假设原始符号是从有限的字母表中提取的。他还假设符号可以在“记忆位置”被刻写或擦除。图灵模型的工作原理如下：有无限多个存储位置，以线性结构排列。打个比方，这些存储位置是无限长“纸带”上的“单元”。更确切地说，存储位置可以在各种介质（例如硅芯片）中物理实现。有一个中央处理器，它一次可以访问一个内存位置。打个比方，中央处理器是一台“扫描仪”，沿着纸带一次移动一个“单元”。中央处理器可以进入有限多个机器状态。中央处理器可以执行四种基本操作： 在内存位置写入符号；从内存位置擦除符号；访问线性数组中的下一个内存位置（“移到磁带上的右侧”）；访问线性数组中的前一个存储位置（“移到磁带上的左侧”）。中央处理器执行哪种基本操作完全取决于两个事实：当前存储位置当前刻有哪个符号；以及扫描仪自身当前的机器状态。机器表规定了中央处理器在给定其当前机器状态和当前正在访问的符号的情况下执行哪些基本操作。机器表还规定了中央处理器的机器状态在给定这些相同因素的情况下如何变化。因此，机器表保存了管理计算的一组有限的常规机械指令。图灵将这种非正式的描述转化为严格的数学模型。有关更多详细信息，请参阅图灵机条目。图灵通过反思理想化的人类计算代理来激发他的方法。他引用了我们的感知和认知装置的有限性，认为人类执行的任何符号算法都可以由合适的图灵机复制。他的结论是，图灵机形式主义尽管极其简单，但足够强大，可以通过符号配置捕获所有人类可执行的机械程序。随后的讨论者几乎一致同意。图灵计算通常被描述为数字计算而不是模拟计算。这意味着什么并不总是那么清楚，但基本思想通常是计算在离散配置上进行。相比之下，许多历史上重要的算法都是在连续可变的配置上运行的。例如，欧几里得几何学对尺子和圆规结构赋予了很大的作用，它可以操纵几何形状。对于任何形状，人们都可以找到另一种具有任意小程度差异的形状。图灵机操纵的符号配置不会有任意小的差异。图灵机对从有限字母表中提取的离散元素（数字）字符串进行操作。一个反复出现的争议涉及数字范式是否非常适合模拟心理活动，或者模拟范式是否更合适（MacLennan 2012；Piccinini 和 Bahar 2013）。 [1] 除了介绍图灵机之外，图灵（1936）还证明了涉及图灵机的几个开创性的数学结果。特别是，他证明了通用图灵机（UTM）的存在。粗略地说，UTM 是一种可以模仿任何其他图灵机的图灵机。其中之一为 UTM 提供符号输入，该符号输入对图灵机 M 的机器表进行编码。 UTM 复制 M 的行为，执行 M 的机器表中包含的指令。从这个意义上说，UTM 是一台可编程通用计算机。初步估计，所有个人计算机也是通用的：它们可以模仿任何图灵机