(转)“逻辑”和“程序”浅释

“逻辑”和“程序”浅释

By: 庄朝晖 发表于 2005-9-12 11:40:57

logic溯源
logical 来自名词logic，logic又来自中古拉丁文的logica，logica又源自希腊文logos（λóγｏｓ）。logos一般翻译为“逻格斯”，接近于中文里的“道”。
中 文里，“道”的原始意义是路。后来引申为行事之路，以及所行之事之路，成为一个抽象名词“道”，指称各种活动以及事物的法术、规范、法则等等。如“吾不知 其名强名曰道”、“王道”和“盗亦有道”。在汉语中，道字除了上述的一切意义外，还有一个常用的意思，就是谈说。如“道可道，非常道”里的第二个道。
逻 各斯是由赫拉克利特首先引入哲学的。从他的著作残篇和别人引述中可以看到，他时而说逻各斯是创生世界的种子，时而说它是万物变化的尺度，有时则简单地等于 讲演，有时又似乎用如声望，充分表现出一个新范畴常有的那种性格的不确定性。后来在亚里士多德手里，逻各斯多被用来表示事物的定义或公式，以致铸成了西方 各门学科的名字都以 -logy缀后的习惯。所有这些，以及由此更引申开去的哲学的、神学的种种解释，什么万物的本元，宇宙的灵魂，人神的媒介，以及理性、判断、根据、关系等 等，万变不离其宗，都并未跳出言谈及以言谈展示所谈让人来看这个原始樊篱（参见海德格尔《存在与时间》第七节）。 （以上参考庞朴《解牛之解》）
“逻格斯”的基本含义为言谈。在言谈和辩论中，渐渐发展出逻辑学这一领域。从地域来分，古代逻辑学可以分为希腊逻辑学（亚里士多德），印度逻辑学（因明学）和中国逻辑学（墨子名学）。
在以往，逻辑学是哲学的一个分支。1800中期后，逻辑学也成为数学的一个分支。近代以来，逻辑学成为计算机科学的重要基础。根据应用的领域，逻辑可以分为哲学逻辑，数理逻辑和计算逻辑。
程序：
程序：算法在计算机上的实现。对于特定的程序语言来讲，程序即符合该语言语法的语句的有限系列。
所 谓算法，是对特定问题求解步骤的一种描述，它是指令的有限序列，其中一条指令表示一个或多个操作。值得注意的是，算法刚提出时是一个模糊的直观的概念。后 来，又出现了Turing命题和Church命题。所谓Turing命题，即算法是Turing可计算的。所谓Church命题，即算法是递归可计算的。 后来证明，Turing可计算的等价于递归可计算的。所以，Turing命题和Church命题也合称Church－Turing命题。该命题是对算法概 念的一个更严格的刻画。当今的计算机，尽管硬件速度越来越快，它们的理论背景仍旧是Turing机。所以，它们的计算机能力也还在Turing可计算的范 围内。
算法具有下列特性：有穷性，确定性，可行性，有相关联的输入和输出（正确性）。
在我看来，计算机科学主要关注两个问题：一是什么问 题是可计算的，另一个是如何计算得更快。在第一个层面，我们把一些原来以为不可计算的问题可计算化，如机器博弈，自动定理证明，机器翻译等等。在这个层 面，关注计算的效果能否达到要求（如机器下棋能否超过人类，机器翻译能否进入实用领域）。在第二个层面，我们追求如何用尽量少的资源（时间空间等）来求解 问题。在这个层面，关注计算的复杂性问题（复杂性分析，实验数据分析）。当然，这两个层面，也经常是混合在一起的。
逻辑与程序：
　　那么，逻辑在什么程度上是可以计算的？也就是说逻辑与程序又存在什么关系？
　 　在更一般层面上，逻格斯与算法也具有一定的关系。举个例子，人工智能的测试离不开言谈。所谓的图灵测试，我们也可以这样理解。把一位具有人类外形的机器 人放到人群中去，在言谈交往中，看我们是否能够把它辨别出来。如果不能，该机器人就达到人类智能的水平。图灵测试的标准不外还是言谈，或者更多的也可以是 言谈举止。
　　在逻辑与程序层面，我们知道，命题逻辑是可以判定的。也就是说，任给一个命题公式，存在一个能行的算法判断出该公式是恒真的，恒假 的或者是可满足的。但是，一阶逻辑只是半可判定的。也就是说，存在一个能行的算法，该算法对于任意给定的公式来说，如果该公式是恒真的，算法能够成功结 束。否则算法不停机。另外，还可以对一阶系统加入一些限制条件，在这些限制条件下，该系统也可以是可判定的，也就是可计算的，比如基于HORN字句的 PROLOG语言就是一门逻辑程序设计语言，还有目前正在研究的一些扩充逻辑程序语言（如回答集等）。

2005年9月12日于厦门大学