计算科学的根本问题
http://bbs.xml.org.cn/dispbbs.asp?boardID=64&ID=50970
科学问题是指一定时代的科学认识主体（人），在已完成的科学知识和科学实践的基础上，提出的需要解决并且有可能解决的问题。它包括一定的求解目标和解域，但是尚无确定的答案。人类科学进步的历史，就是一个不断提出科学问题又不断解决科学问题的历史。
并非关于科学的任何问题都能称为科学问题。科学问题的主要特征包括：
l 时代性，任何一个科学问题都具有它的时代特征。
l 混沌性，科学问题的提出，表明已有知识已经难以满足人们探索世界的需要，人们渴望新知识的追求，但是，开始的时候是模糊不清的。
l 可解决性：科学问题必须是有可能被解决的。
l 可变异性：如果一个问题能引出另外的具有可解决性的科学问题，则原问题仍然是科学问题。
l 可待解性：科学问题是尚未解决的问题。
很早以前，我国古代学者就认为，对于一个数学问题，只有当确定了其可用算盘解算它的规则时，该问题才是可解的。这已经体现了算法化思想，已经包含着我国古代学者对计算的根本问题，即“能行性”问题的朴素的理解。
到了中世纪，哲学家提出一个大胆的问题：能否用机械来实现人脑活动的个别功能[K2] 。这直接导致了后来能进行简单数学运算的机械计算机器的发明和制造。包括，
l 1641年，法国人B.Pascal利用齿轮技术制成第一台加法机；
l 1673年德国人G.W.V.Leibniz在Pascal的基础上制造出能进行简单四则运算的计算机器。
l 19世纪30年代，英国人C.Babbage设计了用于计算对数、三角等算术函数的分析机。
l 20世纪20年代，美国人V.Bush研制了能解一般微分方程组的电子模拟计算机。
这一计算的历史，包含着人们对计算过程的本质和计算的根本问题的探索。
然而，是形式化方法和理论研究计算本质认识取得了突破性进展。的发展，最终促使人们对
形式化方法和理论的研究起源于对数学的基础研究。数学的基础研究是指对数学的对象、性质及其发生、发展的一般规律进行科学研究。其中有四个重要的标志性工作。
第一个是德国数学家G.Cantor在1874年提出的集合论，成为近代数学的基础。
第二个是1901年B.Russel在集合论基础上提出的罗素悖论，直接导致了数学发展历史上的第三次危机。罗素悖论的形式化定义是S＝{x|x不属于S}。
为了消除悖论，挽救数学大厦的基础，数学基础研究逐步形成了逻辑主义、直觉主义和形式主义三大流派。20世纪初，形式主义流派的代表人物、大数学家D.Hilbert提出了著名的“希尔伯特纲领”，成为第三个标志性工作。希尔伯特纲领提出：将每一门数学分支形式化，构成形式系统，并以这些形式化了的分支为对象，构建数学的元理论，证明每一个形式系统的相容性，从而导出全部数学的相容性。希尔伯特纲领的实质是要寻找通用的形式化逻辑系统，且该系统应当是完备的，即在该系统中，可以机械的判定任何给定命题的真伪。希尔伯特纲领的基础是逻辑和代数，源于19世纪英国数学家G.Boole创立的布尔代数体系。
不幸的是，1931年，奥地利年仅25岁的数学家哥德尔（K.Godel）证明了关于形式系统的“不完备性定理”，宣告了希尔伯特纲领的失败。这也是数学基础研究中的第四个标志性工作。哥德尔不完备性定理指出，不存在希尔伯特所希望的完备的形式系统，任何形式系统都是不完备的，都不能穷尽全部数学命题，任何形式系统都存在着该系统不能判断其真伪的命题，即任何形式系统中，都存在着不可解的问题。
希尔伯特纲领虽然失败了，但是它和哥德尔不完备性定理一起，促进了人们对于计算科学的本质问题的认识。例如，它启发计算机科学家应当避免花费精力去证明那些不能判定的问题，而应把精力集中到解决具有“能行性”的问题上来。
迄今为止公认的“计算的本质”，最终由图灵揭示出来的。20世纪30年代后期，数学家图灵（A.M.Turning）通过构造理论的图灵机，形式化的阐述了计算的本质，这个本质用自然语言描述为：任何计算，在本质上都可以还原为计算者（人或者机器）对一条两端可无限延长的纸带上的一串0、1进行变换、最终得到一个满足预先规定的符号串的变换过程。图灵的研究成果，是对哥德尔研究成果的深化。该成果表明，存在一些问题，是不能用任何机械过程解决的，即存在一些问题，是图灵机无解的。由于任何数值和非数值（字母、符号等）对象都可以编码成字符串，它们既可以被解释成数据，又可以被解释成指令，因此，任何计算的过程本身也都可以被编码，并存放在存储器中。
图灵对计算本质的描述，揭示了计算的能行性本质，提出了可计算性的概念。称一个问题是可计算的，当且仅当它是图灵可计算的。而一个问题是图灵可计算的，当且仅当它有图灵机的能行算法解。所谓能行算法解，即它是一个算法，且能被一台图灵机执行并能使该图灵机停机。任何计算问题最终可归结为图灵可计算问题，这便是著名的丘奇-图灵论题。
有了对计算本质的认识，则可理解计算科学的研究内容和根本问题。
计算科学是对描述和变换信息的算法过程进行系统研究的科学领域。它的研究内容包括从算法、可计算性到根据可计算硬件、软件的实际实现问题的研究。
计算科学的根本问题是：什么能被有效地自动化，即对象的能行性问题。
凡是与能行性有关的讨论，都是处理离散对象的。因为连续对象很难进行能行（自动化）处理[K4] 。因此，“能行性”，这一计算科学的根本问题决定了计算机本身的结构和它处理的对象都是离散的。连续对象必须经过离散化后，才能被计算机处理。可以更为直接的说，计算科学的所有分支领域的根本任务就是“计算”，实质就是字符串的变换。
数学是科学之母，计算机科学更是从离散数学发展来的，ＣＳ主要研究的是形式化的算法。因为形式算法保证了计算机的能行性[K6] ；构造性数学是它的理论基础，因为计算机算法都是构造性[K7] 的。
计算理论是对计算机的本质的抽象描述，它也是理论计算机科学的核心内容；而非数值的组合算法是计算机的灵魂，也是计算机能应用广泛的根本保证，（它把世间万物的逻辑关系做了高度的数学抽象，形成算法类，程序就是基于这些算法类的[K8] ），所以它是计算机科学的核心内容；相对而言，数值计算方法对ＣＳ就次要的多，它更多是科学计算的需要。
[K1]计算科学的根本问题
[K2]大胆的问题
[K3]指令（即操作过程）也可以被编码！！
[K4]为什么连续对象很难进行能行（自动化）处理？？？
[K5]！！！实质是字符串变换？！！
[K6]能行性
[K7]构造性是什么意思？