计算-一个新的哲学范畴(一)

范畴论是数学中的一个重要概念，它涉及到对象和关系的抽象化。

范畴是数学中的一个重要结构，它提供了在数学对象之间进行操作的方式。

在范畴论中，对象被视为元素集合，而关系则被视为这些元素之间的映射。

以下是一个简要的讲义，涵盖了范畴论的基本概念和主要内容：1. 范畴的定义和基本结构范畴是对象和态度的集合，其中对象是数学对象的一般化，而态度则表示对象之间的关系。

在范畴中，对象之间的映射被称为态射。

态射的集合是态度的集合，而态度的集合是对象的集合。

基本结构包括对象之间的态射以及态射之间的复合。

态射之间的复合定义了态度的传递性质。

2. 函子函子是一种特殊类型的范畴对象，它表示从一个范畴到另一个范畴的映射。

函子可以用于将不同的数学结构进行比较和转换。

3. 自然变换自然变换是在两个函子之间定义的一种关系，它表示两个函子之间的相似性。

自然变换可以用于描述两个数学结构之间的相似性或差异。

4. 逆象和余象逆象和余象是范畴中的重要概念，它们表示态射的反向映射。

逆象和余象可以用于描述对象之间的关系和操作。

5. 限制和投射模限制和投射模是范畴论中的另一个重要概念，它们表示对态射的限制和投射操作。

这些操作可以用于对对象进行分类和分解。

6. 上下同态与上下同构上下同态和上下同构是范畴论中的重要概念，它们表示两个范畴之间的等价关系。

这些关系可以用于对数学结构进行分类和组织。

以上是范畴论的基本概念和主要内容。

范畴论在数学中有着广泛的应用，它可以帮助我们更好地理解数学对象之间的关系和操作，以及不同数学结构之间的相似性和差异。

请注意，以上内容仅是一个简要的讲义，范畴论是一个非常深奥和复杂的领域，需要进一步的学习和实践才能完全掌握。

谈谈你对哲学的认识（哲学的含义、哲学的性质、哲学的功能、哲学与其他科学的关系)并谈谈学习哲学对当代大学生的现实指导意义哲学的含义哲学,是理论化、系统化的世界观，是自然知识、社会知识、思维知识的概括和总结,是世界观和方法论的统一.是社会意识的具体存在和表现形式，是以追求世界的本源、本质、共性或绝对、终极的形而上者为形式，以确立哲学世界观和方法论为内容的社会科学。

源出希腊语philosophia,意即“热爱智慧”。

社会意识形态之一，是关于世界观的学说。

是自然知识和社会知识的概括和总结。

哲学的根本问题是思维和存在、精神和物质的关系问题，根据对这个问题的不同解释而形成两大对立派别:唯心主义哲学和唯物主义哲学。

可以归纳为：●哲学是理论化、系统化的世界观、是世界观的理论体系；●哲学是关于自然知识、社会知识和思维知识的概括和总结;●哲学既是理论化的世界观,又是方法论，是世界观与方法论的统一；哲学的性质哲学是科学的科学；是科学之王;是艺术之母。

哲学是关于世界观的学说，是具体知识的概括和总结,是世界观和方法论的统一。

哲学是时代精神的精华，是关于世界观和方法论的学问。

哲学的基本问题是思维和存在的关系问题.（一）哲学是使人聪明的学问在古希腊语中，“哲学”是“爱智慧”的意思,是使人聪明的学问。

为什么？这是因为：1、哲学是理论化、系统化的世界观2、哲学是自然知识、社会知识和思维知识的概括和总结3、哲学是世界观和方法论的统一(二）哲学是大智慧亚里士多德：哲学并不是一门生产知识,因此，人们研究哲学是为了摆脱无知和追求智慧，而不是为了实用。

总之，哲学是大智慧，是大学问，懂了哲学道理，就抓住了事物的根本。

哲学是大智慧，是大学问。

它不是一种实用技术，但是，不实用并不等于无用。

哲学的功能哲学的主要内容是：唯物论;辩证法；唯物史观，研究对象是客观现实世界社会历史发展及精神世界功能:1.指导认识改造世界。

2.指导生活实践。

3.为人们提供人生观价值观的指导。

范畴论是一门抽象数学中极其重要的学科，它的研究对象是数学中各种数学结构之间的关系和转化。

范畴论不仅仅是一种重要的工具，更是一种哲学思想方式。

范畴论的核心概念是“范畴”，范畴是由对象和态射组成的，其中对象可以是任意的数学结构，而态射则表示对象之间的关系和转化。

范畴论的基本思想是认为数学中的各种结构和概念都可以通过对象和态射的组合来描述和研究，从而揭示了数学的内在联系和本质。

范畴论的研究方法是通过定义和研究范畴、函子和自然变换等概念来研究不同数学结构之间的映射关系。

函子是一种将范畴之间的关系映射为另一种关系的特殊结构，它可以将一个范畴中的对象和态射映射到另一个范畴中的对象和态射上。

自然变换则描述了不同函子之间的关系和转化。

范畴论的研究方法提供了一种抽象的数学语言，使得数学研究者可以更加清晰地描述、分析和证明各种数学结构和概念之间的关系，从而将抽象数学推向了新的高度。

范畴论在数学中的应用非常广泛，几乎涉及到数学的各个分支，如代数学、几何学、拓扑学等。

范畴论提供了一种通用的框架和语言，使得不同数学领域中的各种数学结构和概念可以在一个统一的框架下进行描述和研究。

范畴论的应用不仅仅局限于数学内部，它还与计算机科学、物理学等领域有着广泛的联系和应用。

特别是在计算机科学中，范畴论的概念和方法被广泛应用于编程语言的设计和形式化验证等方面。

范畴论的哲学意义在于它提供了一种更加抽象和普遍的数学思维方式。

通过范畴论，数学研究者可以将各种数学结构和概念抽象为对象和态射，在这个抽象的层面上进行研究和推理。

这种抽象的数学思维方式可以帮助我们更好地理解和解释数学现象，揭示数学的内在联系和本质。

同时，范畴论的哲学思想也在一定程度上改变了传统的数学观念，提供了一种全新的数学语言和思维方式，对于培养抽象思维能力和数学思维能力具有重要意义。

总之，范畴论作为一门抽象数学中的重要学科，不仅仅是一种工具，更是一种哲学思想方式。

它通过定义和研究范畴、函子和自然变换等概念，揭示了数学中各种数学结构和概念之间的关系和转化，提供了一种通用的框架和语言，推动了抽象数学的发展。

第1章引论本章要点：1.什么是计算；2.计算机科学与计算科学的区别；3.来自计算机发展史的启示；4.计算机应用；5.计算机发展趋势。

1.1 什么是计算？简单计算，如我们从幼儿就开始学习和训练的算术运算，如“3 + 2 = 5”“3 2 = 6”等，是指“数据”在“运算符”的操作下，按“规则”进行的数据变换。

我们不断学习和训练的是各种运算符的“规则”及其组合应用，目的是通过计算得到正确的结果。

广义地讲，一个函数如“”把x变成了f(x)就可认为是一次计算，在高中及大学阶段我们不断学习各种计算“规则”并应用这些规则来求解各种问题，得到正确的计算结果。

如对数与指数、微分与积分等。

“规则”可以学习与掌握，但应用“规则”进行计算则可能超出了人的计算能力，即人知道规则但却没有办法得到计算结果。

如何解决呢？一种办法是研究复杂计算的各种简化的等效计算方法(数学)使人可以计算，另一种办法是设计一些简单的规则，让机械来重复的执行完成计算，即考虑能否用机械来代替人按照“规则”自动计算。

例如：能否机械地判断方程“a1x1b1+a2x2b2+…+a n x n b n = c”是否有整数解?”，即机械地证明一个命题是否有解? 是否正确?类似的上述问题，促进了计算机科学和计算科学的诞生和发展，促进了人们思考：◆什么能够被有效地自动计算？现实世界需要计算的问题是很多的，哪些问题是可以自动计算的，哪些问题是可以在有限时间有限空间内自动计算的？这就出现了计算及计算复杂性问题。

以现实世界的各种思维模式为启发，寻找求解复杂问题的有效规则，就出现了算法及算法设计与分析问题。

例如观察人的思维模式而提出的遗传算法、观察蚂蚁行动的规律而提出的蚁群算法等。

◆如何低成本、高效地实现自动计算？如何构建一个高效的计算系统：计算机器的构建问题和软件系统的构建问题。

◆如何方便有效地利用计算系统进行计算？利用已有计算系统，面向各行各业的计算问题求解。

什么能、且如何被有效地自动计算问题就是计算学科的科学家不断在研究和解决的问题。

哲学概念知识哲学概念---陈才天---什么是哲学？即哲学概念是什么？怎样定义哲学概念，古今中外哲学人有数十种不同的表述。

笔者认为，哲学概念应抽象得出哲学作为一门学科的内涵、性质和特征，因此，哲学是认识论本体论人性论方法论相互联系的逻辑反思的理论。

现在，我根据这一哲学概念对哲学的内涵、特征、性质等做出简要的阐述。

一、哲学的内涵哲学工作专家们在各自编制的哲学教科书中，对于哲学作为一门学科所包括的内容，在结构内涵上大体是一致的，但具体的学科门类却有所不同。

俞吾金先生说：“哲学是认识论、形而上学和方法论”。

魏志明等人编《哲学引论》是“形而上学，认识论，伦理学和美学。

”台湾邬昆如主编《哲学概论》是“认识论，形而上学和价值哲学。

”我将“形而上学”列为一种方法论，将“价值哲学”，“伦理学”和“美学”等列为“人性论”，所以认为：认识论、本体论、人性论和方法论是哲学内涵所包括的范围，其理由如下：（一）认识论的内容：认识论即知识论，是关于人类认识的发生与发展问题的理论。

它探讨人类认识的起源、本质、历程、界限、认识主体与认识对象关系和知识真理性等方面的理论或学说。

在中国认识论向来不发达，但并非没有过认识论。

古籍《大学》曰：“致知在格物。

物格而后知至，知至而后意诚。

”应是中国认识论的萌芽或滥觞，但直到宋明理学，程颐、朱熹、王阳明等人有较详尽的认识论思想观点，但未曾形成系统性认识论理论或学说。

现代认识论的代表著作是金岳霖《知识论》。

在古希腊哲学中，苏格拉底和柏拉图主要是形而上的本体论哲学，认识论的代表作是亚里士多德《工具论》的五本小书：《范畴》、《分析前论》、《分析后论》、《论诠释》和《论题》。

但这并非真正意义上的认识论。

在人类认识史上，自笛卡尔提出“我思故我在”始，第一次形成了真正的认识论研究。

近代西方认识论，主要表现为经验论与唯理论的对立与争论。

经验论认为，一切认识（知识）都是思维从感官经验的感性内容中归纳、概括、抽象出来的。

第2章可计算性理论基础可计算性理论(computability theory) 是研究计算的一般性质的数学理论，也称算法理论或能行性理论. 可计算理论的重要课题之一就是通过建立计算的数学模型给出“计算”这一直观概念的数学描述，并明确区分哪些是可计算的，哪些是不可计算的.“计算”是人类基本的思维活动和行为方式, 也是人们认识世界与改造世界的基本方法. 随着计算机的诞生和计算机科学技术的发展, 计算技术作为现代技术的标志, 已成为世界各国许多经济增长的主要动力, 计算领域也已成为一个极其活跃的领域. “计算”作为一门学科是在上个世纪末才为人们真正认识的，这要归功于美国计算机学会（简称ACM）和美国电气和电子工程师学会计算机分会（简称IEEE-CS）组成的联合攻关组成员的艰苦卓绝的工作①. 目前，计算学科正以令人惊异的速度发展, 并大大延伸到传统的计算机科学的边界之外, 成为一门范围极为宽广的学科②. 如今, “计算”已不再是一个一般意义上的概念, 而是“各门科学研究的一种基本视角、观念和方法, 并上升为一种具有世界观和方法论特征的哲学范畴”③.可计算性理论是计算机软件与理论的重要组成部分之一，也是计算机科学的理论基础. 20世纪30年代图灵在可计算性理论方面取得的研究成果，对后来出现的存储程序计算机(即冯·诺伊曼型计算机) 的设计思想产生了重要影响. 目前，可计算性理论的基本概念、思想和方法已被广泛应用于计算机科学的各个领域，如算法设计与分析、计算机体系结构、数据结构、编译方法与技术、程序设计语言语义分析等.在本章中, 我们不仅能了解到计算概念的形成与发展, 弄清计算的本质, 而且能感受数学的魅力和数学家们在建立可计算性理论基础过程中所展现出的聪颖与智慧. 通过本章的学习, 要充分认识可计算性概念本质, 深入理解可计算性概念数学表示和定义的基本思想方法, 初步弄清各类可计算性函数之间的关系, 重点掌握递归函数的基本概念与基本性质.§1 计算概念的形成与发展计算概念的形成与发展经历了漫长的历史，它是计算科学思想史研究的主要线索之一. 尽管目前我们还无法考证人类究竟是从什么时期开始计数和进行数的运算，但从现有的考古发现和有文字记载的史料中，我们仍然可以捕捉到早期人类在计算领域取得的成就以及从中体现出的人类智慧. 在《力量—改变人类文明的50大科学定理》一书中，作者将公式“1+1=2”列为之首是有充分道理的，人类对数的可加性的发现和推广应用正是数学科学的全部根基④. 计算概念的形成与发展目前尚无系统的研究结果，我们不妨从以下几个方面加以认识.一、计算概念的初识—抽象思维的进步人类的计算是伴随着人类文明的起源和进步而产生和发展的. 最初计算的表现形式是“计数”，“数”的概念是人们通过计数认识的. 在漫长的进化和发展过程中，人类的大脑逐渐具有了①Denning P J, et al. Computing as a discipline. Communications of the ACM [J]. 1989, V ol.32(1).②董荣胜, 古天龙. 计算机科学技术与方法论[M]. 北京: 人民邮电出版社, 2002.③郝宁湘. 计算: 一个新的哲学范畴. 哲学动态[J]. 2000年第11期.④李啸虎, 田廷彦, 马丁玲. 力量—改变人类文明的50大科学定理[M]. 上海: 上海文化出版社, 2005.一种特殊的本领，这就是把直观的形象变成抽象的数字，进行抽象思维活动. 正是由于能够在“象”和“数”之间互相转换，人类才真正具备了认识世界的能力. 从“计数”到“数”的概念形成，是人类在抽象思维领域中迈出的辉煌一步.考古发现最早人类留有计数痕迹的东西是一些带有刻痕的骨头，这些骨头出土于欧洲西部，距今已有2万至3万年的历史，当时生活在这一地区的是奥里尼雅克（Aurignacian）时期（法国旧石器时代前期）的克罗麦昂（Cro-Magnon）人. 把形象事物以刻痕的形式表示并记录在骨头上，表明当时的人类已或多或少地认识了“映射”的概念，而这一概念却是数学科学中最为基本也是十分重要的一个概念. 人类最早使用计数系统的证据，是1937年在捷克斯诺伐克（Czechoslovakia）出土的2万年前的狼的颚骨，颚骨上“逢五一组”，共有55条刻痕. 这样的计数方式被人类延用至今，“正”字计数法便是例证.研究地球的构造和历史的地质学家和观察人类的体质和社会特征的人类学家向我们提供了早期人的种种遗迹，他们通过地层里各时期的堆积物的相对位置来估测远古至今各个时代的顺序，并以此来探索人类科学的起源①. 另一方面，研究科学思想史的科学家们则倾向于从自然科学最初形成的学科体系中寻觅人类科学思想史的根源，认为：“古代科学最先发展起来的是天文学与数学，其次是力学，此外还有一些生物学与医学方面的研究，因为这几个学科同古代人类的生产与生活关系最为密切.”②然而，如果没有更早期人类对数的认识、数的表示和数的计算等方面取得的成就，无论是在古埃及通过人们反复测量土地诞生的最初的几何学，还是古巴比伦人最早认识的“金星运动周期”和对日食、月食的预报，都是不可能的，这是一个可想而知的事实. 令人遗憾的是，在如今的诸多科学史和科学思想史研究的著作中，这一点往往被忽视了.二、计算概念的定义—计算本质的揭示在数学科学领域，与“计算”密切相关的概念之一是“算法”，任何计算都是在一定算法支持下进行的. 公元前3世纪，古希腊和中国的数学家就有了算法的概念，象当时的欧几里得辗转相除法就是最好的例子. 大约在公元9世纪初期，阿拉伯著名数学家、天文学家和地理学家花剌子密就给出了现在人们所熟悉的自然数运算规则. 在一个相当长的时期里，人们把“确定关于数学对象（如整数、实数、连续函数等）的各种命题是否正确”作为数学的基本任务. 随着社会的发展以及生产实际的需要，人们逐步开始关心另一类数学任务，“其中之一是在数学发展早期就被认为有极大的重要性，而且至今还在产生着具有重大数学意义的问题，即解决各种问题的算法或能行的计算过程的存在性问题.”③然而，要想真正解决这一问题，就必须对“计算”的概念有一个清楚的认识. 到了20世纪30-40年代，一些著名的数学家几乎同时完全独立地给出了相当于能行可计算函数概念的各种确切定义，其中包括Church的 -可定义性概念④，Herbrand-Gödel-Kleene的一般递归性概念⑤，Turing的可计算性概念⑥等, 经证明，这些形式上完全不同的概念是等价的. 随着计算机的出现和计算机程序设计语言的发展，到了20世纪50-60年代，人们又从不同的角度给出了可计算性函数的一些定义，其中有基于基本字符集算法的Markov①丹皮尔著, 李珩译. 科学史及其与哲学与宗教的关系（第四版）[M]. 北京: 商务出版社, 1987.②林德宏. 科学思想史[M]. 南京: 江苏科学技术出版社, 1985.③戴维斯著, 沈泓译. 可计算性与不可解性[M]. 北京: 北京大学出版社, 1984.④Church A. The Calculi of Lambda-conversion [M]. Princeton : Princeton University Press, 1941.⑤Kleene S C. General Recursive Function’s of Natural Numbers. Mathematische Ann.[J]. 1936 (112): 727-742.⑥Turing A M. On Computable Numbers, with an Application to the Entscheidungs problem. Proceedings of LondonMathematical Society [J]. 1936-1937(45-46): 230-256, 544-546.可计算函数，以及基于URM理想计算机的Shepherdson-Sturgis可计算函数等. 同样，后两者所描述的可计算函数类与前面所提到的是相一致的①.三、计算概念的发展—计算方式的进化人们在计算领域的探索和追求，导致了计算工具的发展，而计算机工具的发展，特别是电子计算机的出现以及它在各个领域的广泛应用，又促进了计算方式的不断进化. 人类的计算方式已由早期的手工和机械方式，进化到了现代的电子计算方式. 计算理论如何发展，计算方式如何进一步演变，是当今人类十分关注的问题. 20世纪90年代，美国计算机科学家Adleman博士在美国《科学》杂志上发表文章，针对组合数学的有关问题，提出了分子计算模型，即DNA计算模型，并以解决7个结点的Hamilton问题为实例，成功地在DNA溶液的试管中进行了运算实验②. 与此同时，量子计算在理论上取得重大进展. 量子计算概念是由美国阿冈国家实验室的Paul Benioff 在20世纪80年初提出的③. 到了1994年，Bell实验室的应用数学家Peter Shor于当年IEEE基础计算理论年会发表突破性工作——快速整数因数分解方法④，使量子计算的潜在应用实力迅速引起广泛关注. 虽然DNA计算和量子计算目前在理论上尚在雏形，但是我们相信，随着历史的前进和人类科技的进步，人们在新型计算机理论研究与应用方面必将取得辉煌的成就, 这些成就将表明：人类在计算领域的探索是永无止境的，其前景是广阔的.在本章接下来的小节和段落中，我们将从基于URM理想计算机的Shepherdson-Sturgis可计算性函数描述和Herbrand-Gödel-Kleene一般递归函数的定义两个方面来介绍可计算性理论的基本知识.§2 算法与能行过程“计算”是解决问题的最基本手段. 随着计算机科学与技术的发展，“计算”的内涵与外延均发生了巨大的变化，其应用范围涉及到了社会发展的各个领域. “计算”离不开计算的规则与方法，正确的计算规则建立与可行的计算方法设计是正确地解决问题的关键所在. 这其中便涉及到“算法”的概念.一、算法概念的由来“算法”在中国古代文献中称为“术”，最早在《周髀算经》、《九章算术》等数学名著中均有充分体现，如《九章算术》中给出的四则运算，求最大公约数、最小公倍数、开平方根、开立方根的方法，求素数的埃拉托斯特尼筛法以及线性方程组求解方法等等，都是为现代人所熟悉的算法.现代人们普遍使用的英文算法Agorithem一词与阿拉伯数学家花剌子密以及他在代数和算术领域作出的重要贡献密切相关. 花剌子密是生活在8世纪末9世纪初波斯的一位数学家、天文学家及地理学家，也是当时巴格达智慧之家的学者. 花拉子米在数学领域最主要贡献是他在9世纪①Cutland N. Computability-An introduction to recursive function theory [M]. London: Cambridge Uni. Press, 1980.②Adleman L. Molecular computation of solutions to combinatorial problems. Science[J]. 1994(266-11): 1021-1024.③Benioff P. The computer as a physical system: A microscopic quantum mechanical Hamiltonian model of computersas represented by Turing machines, Journal of Stat. Phys.[J]. 1980(22): 563-591.④Shor P W. Algorithms for quantum computation: discrete log and factoring. Proc. of the 35th Annual Symposium onFoundations of Computer Science ( IEEE Computer Society Press, Los Alamitos, CA), 1994: 12.30年代完成的著作《代数学》，该书首次系统地给出了解决一次方程及一元二次方程的理论与方法，大为扩阔了此前的数学概念，为数学的发展开辟了一条新路径. 正是因为在代数领域的特殊贡献，是他获得了“代数创造者”的殊荣，这一美誉与较之早500多年的古希腊数学家丢番图所获得的“代数之父”美称齐名. 花剌子密在数学领域的另一项重要贡献是关于“算术”的. 在825年他所著的《印度数字算术》一书中，采用了印度-阿拉伯数字系统，即十进制进位制的记数系统，并给出了数的运算规则. 花剌子密在印度数字方面的著作被翻译成拉丁文，并在中世纪时传入中东和西方，对西方中世纪的科学发展起了重要的作用. 《印度数字算术》的拉丁语翻译是“Algoritmi de numero Indorum”，而花剌子密的拉丁文音译则为Algorithm，其中包含了“花剌子密”运算法则之意，此便是英文中“算法”一词的由来. 如今Algorithm已由一个数学家名字的音译变成了一个十分重要的数学概念.二、算法概念的描述迄今为止，尚无算法概念的确切定义，这是因为几乎所有问题的解决方法都可由所谓的算法来描述. 面对问题的多样性和复杂性，当我们试图用语言对“变化莫测”的算法给出一个系统而又明确的定义的时候，总有“此消彼长”或“顾此失彼”的感觉. 对此，人们通常以“共性”的特征给出算法的一般性描述，而在特定的学科或应用领域将相关的算法概念具体化.算法（Algorithm）是解决一类问题方法，可以理解为由基本运算及规定的运算顺序所构成的完整和有限的解题步骤. 算法的执行过程是针对一类问题中的特例而进行的，即能够对一定规范的特定输入，在有限时间内获得所要求的输出结果，从而达到解决问题的目的.算法的表示方法很多，通常有自然语言、伪代码、流程图、程序设计语言、控制表等. 用自然语言描述算法往往显得冗长且容易引起歧义，因此很少用于在技术层面上较为复杂的算法描述；伪代码、流程图和控制表等以结构化的方法来表示算法，可以避免自然语言描述中普遍存在的二义性问题，因而是算法表示的常用工具；用程序设计语言的主要目的就是通过对算法进行编程使之在计算机上得以实现.在实际应用中，算法应具有以下几个方面的特征:（1）输入项：一个算法有0个或多个输入，是算法执行的初始状态，一般由人为设定. 0输入的情形通常发生在算法的初始状态由算法本身来设定的情况下.（2）输出项：一个算法必须有一个或多个输出，以反映算法对输入数据加工后的结果. 没有输出的算法是毫无意义的.（3）明确性：算法的描述必须无歧义并且每一步骤都有确切的定义，以保证算法的实际执行结果是正确的并能符合人们的希望和要求.（4）可行性：也称有效性或能行性. 算法中描述的任何计算步骤都是通过可以实现的基本运算的有限次执行来完成的，或从直观上讲，每个计算步骤至少在原理上能由人用纸和笔在有限的时间内完成.（5）有穷性：算法有穷性是指算法的执行过程必须在有限的步骤和时间内终止.注意：满足前四个特征的一组指令序列在实际应用中不能称为算法，只能称为计算过程. 例如：计算机的操作系统就是一个典型的计算过程，操作系统用来管理计算机资源，控制作业的运行，没有作业运行时，计算过程并不停止，而是处于“等待”状态.在计算机应用技术领域，算法通常是针对实际问题而设计并且通过编程的手段实现的，其目的是运用计算机解决实际问题，在此情况下，一个无休止运行而无结果的算法是毫无意义的. 因此，在计算机应用领域，掌握算法分析与设计的理论与方法是十分重要的. 一方面，要求我们针对实际问题设计出正确的算法: 如果一个算法有缺陷，或不适合于某个问题，执行这个算法将不会解决这个问题; 另一方面，又要求我们学会选择和改进已有的算法: 同样的问题可以有不同的算法，算法的优劣可以用空间复杂度与时间复杂度来衡量，不断提高算法的效率始终是人们不懈努力的追求. 随着存储技术的发展，最能反映算法效率的时间复杂度已成为人们在算法设计与分析过程中关注的最主要方面之一.注意:算法设计与分析已形成一套较为完整的理论与方法体系, 对于从事计算机应用与开发的工作和技术人员来说, 这些理论与方法是必须掌握的. 目前有大量关于算法设计与分析的文献、专著和教材，然而作为算法设计与分析的基础，我们必须首先要弄清楚的问题是：计算的本质是什么？“可计算”的确切定义是什么？究竟哪些问题是可计算的？这便是“可计算性理论”要回答的问题.三、能行过程与可计算性在数学与计算机科学中，算法又可以说成是一个“能行过程”(effective procedure) 或“能行方法”(effective method). 能行过程是针对“问题”的，通常的说法是“解决某某问题的能行过程”.解决问题的过程是一个问题状态变化的过程，如果我们用参数的形式来描述问题的状态，那么解决问题的过程就可以看成是一个参数变化的过程. 解决问题开始时的状态称为“初始状态”，初始状态的参数称为“输入参数”；解决问题结束时的状态称为“结果状态”，结果状态的参数称为“输出参数”或“输出结果”.对一个问题而言，其“输出结果”与“输入参数”之间的关系应该是明确的. 但允许有下述情形: 有这样的“问题”，它们对输入范围内的有些“输入参数”（有效输入）有明确的“输出结果”，而对有些“输入参数”（无效输入）则没有明确的“输出结果”，甚至“结果”根本就不存在. 对这类“问题”，我们在考虑其能行解决方法时，只要针对有效的输入便可.如果存在解决某问题的能行过程，那么该问题称为是“可解的”或“可计算的”.注意：如果要说明一类问题是“不可解”或“不可计算的”，那么就必须给出该类问题不存在能行过程的证明.我们将通过实例进一步认识“能行过程”的概念.. 求m和n的最大公因子的欧几里得算法可以通过例2-1. 设m和n是两个正整数，且m n下列过程表示:步骤1. 以n除m得余数r. //求余数步骤2. 若0r =, 则输出答案n ，过程终止; 否则转到步骤3. //判断余数是否为0步骤3. 把m 的值变为n , n 的值变为r ，重复上述步骤. //变换参数值分析：上述过程由3个步骤组成，输入参数为正整数m 和n ；每个步骤的描述是明确的并且可以证明过程终止时输出数据为m 和n 的最大公因子；过程的每一步骤都是可以通过一些可实现的基本运算（判断）完成；整个过程经过有穷步后终止. 因此，求m 和n 的最大公因子的欧几里得算法是一个能行过程. 因此，求m 和n 的最大公因子问题是可计算的.例2-2. 考虑函数1()0n g n π⎧=⎨⎩如果小数部分有个连续的数字7； 否则. (2.1)绝大多数数学家会接受g 是合法定义的函数，同时也存在能行的过程逐位生成π小数点后面的数子①. 用k π（）表示π小数点后面第k 位数字，C 作为计数器，则可以采用下面的过程来计算()g n ： 给定n ，首先令()0g n =，计数器0C =，参数1k =.步骤1. 计算()k π. //求π小数点后第k 位数字步骤2. 如果()7k π=，则1C C ←+；否则0C ←. //计数器逢“7”加1，否则清0步骤3. 如果C n =，则输出()1g n =，过程终止；如果C n <，则1k k ←+重复上述步骤. 分析：上述过程同样由3个步骤组成，对给定的输入n ，如果π小数点后面有n 个连续的7，那么过程一定会在有限步终止并输出()1g n =. 问题是：如果π小数点后面没有n 个连续的7，那么上述过程将无休止地运行下去, 而且在任何时候都无法得到我们想要的()0g n =的结论. 因此，上述过程不是能行过程.注意：在例2-2中，虽然我们给出的函数g 的计算过程不是能行过程，但却不能以此断言没有计算函数g 的能行过程. 也许有计算函数g 的能行过程，然而至今尚无人知晓. 有趣的是：如果把例2-2中定义的函数改成如下函数*1()n g n π⎧=⎨↑⎩如果小数部分有个连续的数字7； 否则. (2.2)其中，*()g n =↑表示函数*g 在输入n 时无定义. 那么计算函数g 的过程对于*g 来说就是一个能行的过程. 这是因为对给定的输入n ，如果π小数点后面有n 个连续的7，那么过程一定会在有限步终止并输出()1g n =；如果π小数点后面没有n 个连续的7，那么*()g n 是没有定义的，无需考虑什么“输出结果”的问题.四、停机问题算法也好，能行过程也罢，它们的基本表达形式都可以用一组合适指令（well-defined①Cutland N. Computability-An introduction to recursive function theory [M]. London: Cambridge Uni. Press, 1980: 69.instructions ）的有穷序列来描述. 即在计算机科学领域，他们都可以表示为计算机“程序”. 在第一章中（命题1.17）我们证明了所有的计算机程序之多是可数的，因此可以把所有的程序枚举如下:012,,,,,e P P P P (2.3)其中e P 中的下标e 可视为该程序的编号或编码. 通过上面的分析我们知道，对任意的程序e P 而言，它对某些输入是有明确输出的，运行有穷步后“停机”并给出结果；而对另一些输入可能是没有结果的，并因此进入“死循环”而“不停机”. 因此，我们自然会关心这样的问题:停机问题: 是否存在一个能行过程H ，对任意的程序e P 和输入x ，H 能判断e P 对输入x 是否停机？为了回答这一问题，我们首先要对程序输入与输出的概念做些处理. 程序通常有输入和输出，如果一个程序e P 的输入是x ，那么经运行后e P 的输出可表示为()x e P .运用编码技术，我们可以将程序的输入和输出用自然数表示，因此任何程序都可以视为自然数上的“函数”.命题2.1. 停机问题是不可解的.即不存在能行过程H ，对任意的程序e P 和输入x ，H 能判断e P 对输入x 是否停机.证明: 运用反证法：如果停机问题是可解的，那么就存在能行过程H ，对任意程序e P 和输入x , 当e P 对输入x 停机时有(,)1x e H P =；当e P 对输入x 不停机时有(,)0x e H P =，其中“1”和“0”分别表示“停机”和“不停机”之意.利用H ，我们定义计算过程F 满足: 对任意自然数n ，如果(,)1n H P n =则()()1n F n P n =+；如果(,)0n H P n =则()0F n =.因为过程H 是能行的，所以过程F 也是能行可计算的, 因此计算F 的程序一定会在所有程序的枚举中出现. 设计算F 的程序编号（或编码）为0e ，则F 可表示为0e P ，即对任意的n 均有0()()e F n P n =. 接下来我们考察程序0e P 关于输入0e 的停机情况: 如果程序0e P 关于输入0e 停机，则有00(,)1e H P e =，此时有00000()()1()e e F e P e P e =+≠；如果程序0e P 关于输入0e 不停机，则00()e P e 无定义，由00(,)0e H P e =却可以得到000()0()e F e P e =≠，这和0e P 是计算F 的能行过程矛盾. 此矛盾表明判定停机问题的能行过程是不存在的. ■注意: 需要指出的是：计算过程是可以用“程序”来表述的，一个计算过程是否是能行在于相应 “程序”的运行是否能得到人们所需要的计算结果，所以“能行过程”的概念是针对“程序”的，即能行过程的考察对象是“程序”. 但是，“停机问题”是针对所有“程序”的，它的考察对象因该是所有“程序”的汇集. 据此我们认为，在一般意义下考虑的“能行过程”不能与所谓“停机问题”同“域”而论，否则引起矛盾就难以避免.§3 可计算性概念的数学描述在20世纪以前，人们普遍认为，所有的问题类都是有算法的，人们关于计算问题的研究就是找出解决各类问题的算法来. 随着时间的迁移，人们发现有许多问题虽然经过长期的研究仍然找不到算法，于是人们开始怀疑，是否对有些问题来说根本就不存在算法，即它们是不可计算的.那么什么是可计算，什么又是不可计算的呢？要回答这一问题，最关键的就是要给出“可计算性”概念的精确的定义.到了20世纪30年代，一些著名的数学家和逻辑学家从不同的角度分别给出了“可计算性”概念的确切定义，为计算科学的研究与发展奠定了重要基础. 随着计算机的出现和计算科学的发展，科学家们将“可计算性”概念与“程序设计”思想有机结合，从而使“可计算性”的能行过程更加明显，进一步促进了人们对“可计算性”概念理解和认识. 本节将选择其中的一些描述方法做简单的介绍.因为计算问题均可通过自然数编码的方法用所谓“函数”的形式加以表示，所以我们可以通过对定义在自然数集上的“可计算性函数”的认识来理解“可计算性”的概念.一、递归函数递归函数是递归论这门学科中最基本的概念，其产生可以追溯到原始递归式的使用，如我们现在所熟知的数的加法与乘法. 现代计算机应用技术中，大量的计算过程都是运用递归的形式来描述的，可以说递归技术已经成为计算机科学与技术领域重要的方法工具之一. 递归函数最早的形式是“原始递归函数”（primitive recursive function ）, 因此, 我们首先介绍原始递归函数的概念.1. 原始递归函数原始递归函数是定义在自然数集上的函数，其值域是自然数集的子集. 一般我们用1(,,)n f x x 表示函数f 在变量1,,n x x 处的取值，并称f 为n -元函数. 有时为书写之方便，我们可令1(,,)x n x x =，则函数值1(,,)n f x x 可表示为()x f . 下面是原始递归函数的定义. 按下述规则产生的函数称为原始递归函（I ） 基本函数：下列基本函数是原始递归函数（a ）零函数O ，即对任意的,O()0N x x ∈=；（b ）后继函数S ，即对任意的,S()1N x x x ∈=+；（c ）投影函数P n i ，即对任意的11,,,,0,1,P (,,)N n n i n i n x x n i n x x x ∈≥≤≤=. （II ）合成模式：设1(,,)k f y y 和1(),,()x x k g g 是原始递归函数，其中1(,,)x n x x =. 则运用合成模式产生的函数1()((),,())x x x k h f g g =是原始递归函数.（III ）递归模式：设()x f 和(,,)x g y z 是原始递归函数，其中1(,,)x n x x =. 则运用递归模式产生的函数(,0)(),(,1)(,,(,))x x x x x h f h y g y h y =+=是原始递归函数.1931年，哥德尔在证明其著名的不完全性定理时，给出了原始递归函数的描述，并以原始递归式为主要工具，运用编码技术把所有元数学的概念进行了算术化表示. 原始递归函数的重要性一直受到数学家和逻辑学家的关注和重视. 通常，人们把能够用“纸”和“笔”在有限步里可以计算的函数称为“直观可计算函数”或“可计算函数”. 显然，原始递归函数都是可计算的.例3-1. 证明自然数加法(,)f x y x y =+是原始递归函数.证明: 首先我们注意到自然数集上的恒等函数I()x x =是原始递归函数，因为11I()P ()x x =.。

[计算机论文范文【1】] 计算机论文范文大全集随着计算机的诞生和计算机科学技术的发展，计算技术作为现代技术的标志，已成为世界各国许多经济增长的主要动力。

计算机论文范文【1】 1 引言随着计算机的诞生和计算机科学技术的发展，计算技术作为现代技术的标志，已成为世界各国许多经济增长的主要动力，计算领域也已成为一个极其活跃的领域。

计算学科正以令人惊异的速度发展，并大大延伸到传统的计算机科学的边界之外，成为一门范围极为宽广的学科，人们对计算学科的认识，已从知识层面上升到了方法论的高度[1]。

1989年1月，美国计算机学会(简称acm)和美国电气和电子工程师学会计算机分会(简称ieee-cs)联合攻关组在《acm通讯》杂志上刊登了他们历经4年的研究成果——“作为学科的计算科学”的报告[2]。

该报告围绕计算机的主要现象，从学科的三个基本形态，即理论、抽象和设计入手，结合科学与工程科学两大学科门类的基本特征，完成了计算学科的“存在性”证明，首次给出了计算学科的定义，为“计算”作为学科及其以后的发展奠定了基础。

如今，计算已不再是一个一般意义上的概念，它已成为“各门科学研究的一种基本视角、观念和方法，并上升为一种具有世界观和方法论特征的哲学范畴”[3]。

在长期的社会生产实践中，计算科学的内涵与外延从学科的角度得到进一步诠释，acm 和ieee-cs以及计算机界关于计算学科认知问题的研究不断取得重要成果，其中，cc1991(“计算学科教程1991计划”的简称)和cc2001(“计算学科教程2001计划”的简称)报告为计算学科建立了现代课程体系。

随着计算科学的不断发展，其课程体系也在不断完善，2004年11月，acm、ais和ieee-cs 又联合公布了新的计算学科教程cc2004，文[4]对该课程体系做了分析与思考。

随着信息技术行业人才需求的与日俱增，世界上绝大多数高等院校均设立了计算科学或与之相关的专业，国内的高等院校也不例外。