即思维就是计算.ppt

第2章 计算学科中的科学问题 李陶深 tshli@gxu.edu.cn 2.1 概述 2.1 科学问题的定义 科学问题是指一定时代的科学认识主体，在已完成的科学知识和科学实践的基础上，提出的需要解决且有可能解决的问题。它包含一定的求解目标和应答域，但尚无确定的答案。(例如IPv4——IPv6） 能否在所从事的工作中提出关键和重要的科学问题，对我们每个人来说都是一个挑战。 2.1 科学问题的主要特征 时代性：每一个时代都有它自己的科学问题 混沌性：渴望对新知识的追求，追求开始的时候是模糊不清的。 可解决性 可变异性：能引出另外具有可解决性的科学问题 可待解性：绝非永远不可解决。 2.1 科学问题的方法论作用 科学问题的裂变式作用 如对“数学基础问题”的研究，导致了“形式系统相容性问题”的研究， 最后出现“能行性问题”的研究， 最终于20世纪30年代由图灵、哥德尔、丘奇和波斯特等人共同奠定了计算学科的理论基础 实现了人类对计算认识问题的重大突破。 2.1 科学问题的方法论作用 科学问题的聚变式作用——殊途同归 对不同科学问题的研究最终导致同一科学问题的发现 科学问题的激励作用 它召唤和激励着人们为解决这些富有挑战性的问题而勇往直前。 本章仅对反映计算学科本质的根本问题、学科各领域的基本问题、在学科中起重要作用的典型问题，以及人工智能中的若干哲学问题进行分析。 CH02 计算学科中的科学问题 计算的本质 计算学科的定义及其根本问题 2.2 计算本质的认识历史 康托尔的集合论和罗素悖论 形式化方法和理论的研究起源于对数学的基础研究。 康托尔（G.Cantor，1845～1918）从1874年开始，对数学基础作了新的探讨，发表了一系列集合论方面的著作，从而创立了集合论。 “罗素悖论”，从而导致了数学发展史上的第三次危机。 希尔伯特纲领 希尔伯特（D.Hilbert）在数学基础的研究中提出了一个设想 将每一门数学的分支形式化，构成形式系统或形式理论，并在以此为对象的元理论即元数学中，证明每一个形式系统的相容性，从而导出全部数学的相容性。 目标是要寻找通用的形式逻辑系统，该系统应当是完备的，即在该系统中，可以机械地判定任何给定命题的真伪。 库尔特·哥德尔（K．Godel） 认为《数学原理》所定义的系统既是一致的，也是完备的 任何系统的完备和一致性，可以由系统本身得到证明。 1931年，“希尔伯特纲领”被奥地利逻辑学家Godel搠出一个大窟窿 Godel认为没有一种公理系统可以导出数论中所有的真实命题，除非这种系统本身就有悖论。 推翻“希尔伯特纲领”，还直逼《数学原理》，说它本身就是不一致的。 希尔伯特纲领 “希尔伯特纲领”的研究基础是逻辑和代数，即布尔代数 G?del提出的关于形式系统的“不完备性定理”中指出 这种形式系统是不存在的，从而宣告了著名的“希尔伯特纲领”的失败。 表明形式系统不能穷尽全部数学命题，任何形式系统中都存在着该系统所不能判定其真伪的命题。 希尔伯特纲领的历史意义 “希尔伯特纲领”是在保存全部古典数学的前提下去排除集合论悖论的，它给数学基础问题的研究带来了全新的转机 希尔伯特纲领的提出使元数学得到了确立和发展 希尔伯特纲领的失败启发人们应避免花费大量的精力去证明那些不能判定的问题，而应把精力集中于解决具有能行性的问题。 图灵对计算本质的揭示 “哥德尔定理”的提出使整个逻辑和数学领空中阴云四布。 天才的图灵在数理逻辑大本营的剑桥大学提出一个设想：能否有这样一台机器，通过某种一般的机械步骤，能在原则上一个接一个地解决所有的数学问题。 图灵从计算一个数的一般过程入手对计算的本质进行了研究，从而实现了对计算本质的真正认识。 图灵用形式化方法成功地表述了计算这一过程的本质：所谓计算就是计算者（人或机器）对一条两端可无限延长的纸带上的一串0和1执行指令，一步一步地改变纸带上的0或1，经过有限步骤，最后得到一个满足预先规定的符号串的变换过程。 现代计算机的产生以及计算学科的定义 图灵机反映的是一种具有能行性的用数学方法精确定义的计算模型，而现代计算机正是这种模型的具体实现。 计算学科是对描述和变换信息的算法过程，包括对其理论、分析、设计、效率、实现和应用等进行的系统研究。 来源于对算法理论、数理逻辑、计算模型、自动计算机器的研究，并与存储式电子计算机的发明一起形成于20世纪40年代初期。 计算学科的根本问题 计算学科的根本问题是：什么能被（有效地）自动进行。 “能行性”这个计算学科的根本问题决定了计算机本身的结构和它处理的对象都是离散型的，甚至许多连续型的问题也必须在转化为离散型问题以后才能被计算机处理。例如，计算定积分就是把它变成离散量，再用分段求和的方法来处理的。 计算学科所有