< 上一个 | 内容 | 下一个 >

计算定律(The law of computation

计算是局部的,即计算过程中任何一个动作都是局部操作,而且一个计算就是一系列局部操作构成的序列。


显然,逻辑推理是一个计算过程,计算定律也表明逻辑推理是局部的。

计算是局部的这一计算定律表明:计算完美地实现了逻辑推理,但是不能实现直觉推理。

什么是逻辑推理?什么是直觉推理?逻辑推理就是同一抽象层次的推理。直觉推理就是跨越抽象层谱的推理。现实世界必然包含不同抽象层谱的对象。逻辑推理和直觉推理都是人推理不可或缺的推理形式,是人学习的基本策略。

因此仅仅依靠计算不可能实现人的学习,这是以计算为中心建立学习理论的先天不足,不可弥补。

Turing 机模型揭示了计算概念的实质,更证明任何一个计算可以用一个 Turing 机来实现,然而并没有回答如何对一个问题通过计算来求解。

任何一个计算问题必然有一个“目标函数”。计算的目标函数是


由人来确定的,机器本身不能确定计算的目标函数。

一个计算问题的目标函数是该计算问题的语义,而计算的过程是该计算问题的语法。

因此,一个计算问题有一个人确定的语义和一个机器实现的语法。计算机解决计算问题的语法,但是不能解决计算问题的语义。

Turing 机的定义揭示了计算这一概念的实质,奠定了计算理论的基础。而计算理论正是计算机科学的三大支柱之一。

通用 Turing 机还为后来的电子计算机提供了数学模型,因此,通用 Turing 机也为计算机体系结构提供了原理。体系结构是计算机科学的三大支柱之一。

程序理论、计算理论和体系结构正是计算机科学的三大支柱,其中程序理论的数学基础是数理逻辑,而计算理论和体系结构的数学基础都是Turing 机和通用 Turing 机。

计算这一概念的研究毫无疑问仍然是计算机科学,特别是理论计算机科学的核心问题。计算的数学实质由 Turing Thesis 确定。 这个论题是否正确仍然是一个重大问题。在计算复杂性层面,现有的算法复杂性及计算复杂性都是基于 Turing 机来定义的。基于 Turing 机模型,建立了 NP 困难性、NP 完全性的理论。然而计算复杂性理论并没有揭示一个计算问题为什么困难的实质。一个计算问题为什么复杂应该是由这个问题内在本质属性所决定的。

算法、计算复杂性,甚至可计算性的任何突破实质上都要求有一个算法新思想。这仍然是计算机科学研究的发动机。