第2章可计算性理论基础.doc

《第2章可计算性理论基础.doc》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第2章可计算性理论基础可计算性理论(computabilitytheory)是研究计算的一般性质的数学理论，也称算法理论或能行性理论.可计算理论的重要课题之一就是通过建立计算的数学模型给出“计算”这一直观概念的数学描述，并明确区分哪些是可计算的，哪些是不可计算的.“计算”是人类基本的思维活动和行为方式,也是人们认识世界与改造世界的基本方法.随着计算机的诞生和计算机科学技术的发展,计算技术作为现代技术的标志,已成为世界各国许多经济增长的主要动力,计算领域也已成为一个极其活跃的领域.“计算”作为一门学科是在上个世纪末才为人们真正认识的，这要归功于美国计算机学会（简称ACM）和美国电气和电子工程

2、师学会计算机分会（简称IEEE-CS）组成的联合攻关组成员的艰苦卓绝的工作DenningPJ,etal.Computingasadiscipline.CommunicationsoftheACM[J].1989,Vol.32(1)..目前，计算学科正以令人惊异的速度发展,并大大延伸到传统的计算机科学的边界之外,成为一门范围极为宽广的学科董荣胜,古天龙.计算机科学技术与方法论[M].北京:人民邮电出版社,2002..如今,“计算”已不再是一个一般意义上的概念,而是“各门科学研究的一种基本视角、观念和方法,并上升为一种具有世界观和方法论特征的哲学范畴”郝宁湘.计算:一个新的哲学范畴.哲学动态[

3、J].2000年第11期..可计算性理论是计算机软件与理论的重要组成部分之一，也是计算机科学的理论基础.20世纪30年代图灵在可计算性理论方面取得的研究成果，对后来出现的存储程序计算机(即冯·诺伊曼型计算机)的设计思想产生了重要影响.目前，可计算性理论的基本概念、思想和方法已被广泛应用于计算机科学的各个领域，如算法设计与分析、计算机体系结构、数据结构、编译方法与技术、程序设计语言语义分析等.在本章中,我们不仅能了解到计算概念的形成与发展,弄清计算的本质,而且能感受数学的魅力和数学家们在建立可计算性理论基础过程中所展现出的聪颖与智慧.通过本章的学习,要充分认识可计算性概念本质,深入理解可计算

4、性概念数学表示和定义的基本思想方法,初步弄清各类可计算性函数之间的关系,重点掌握递归函数的基本概念与基本性质.§1计算概念的形成与发展计算概念的形成与发展经历了漫长的历史，它是计算科学思想史研究的主要线索之一.尽管目前我们还无法考证人类究竟是从什么时期开始计数和进行数的运算，但从现有的考古发现和有文字记载的史料中，我们仍然可以捕捉到早期人类在计算领域取得的成就以及从中体现出的人类智慧.在《力量—改变人类文明的50大科学定理》一书中，作者将公式“1+1=2”列为之首是有充分道理的，人类对数的可加性的发现和推广应用正是数学科学的全部根基李啸虎,田廷彦,马丁玲.力量—改变人类文明的50大科学定理

5、[M].上海:上海文化出版社,2005..计算概念的形成与发展目前尚无系统的研究结果，我们不妨从以下几个方面加以认识.一、计算概念的初识—抽象思维的进步人类的计算是伴随着人类文明的起源和进步而产生和发展的.最初计算的表现形式是“计数”，“数”的概念是人们通过计数认识的.在漫长的进化和发展过程中，人类的大脑逐渐具有了一种特殊的本领，这就是把直观的形象变成抽象的数字，进行抽象思维活动.正是由于能够在“象”和“数”之间互相转换，人类才真正具备了认识世界的能力.从“计数”到“数”的概念形成，是人类在抽象思维领域中迈出的辉煌一步.考古发现最早人类留有计数痕迹的东西是一些带有刻痕的骨头，这些骨头出土于

6、欧洲西部，距今已有2万至3万年的历史，当时生活在这一地区的是奥里尼雅克（Aurignacian）时期（法国旧石器时代前期）的克罗麦昂（Cro-Magnon）人.把形象事物以刻痕的形式表示并记录在骨头上，表明当时的人类已或多或少地认识了“映射”的概念，而这一概念却是数学科学中最为基本也是十分重要的一个概念.人类最早使用计数系统的证据，是1937年在捷克斯诺伐克（Czechoslovakia）出土的2万年前的狼的颚骨，颚骨上“逢五一组”，共有55条刻痕.这样的计数方式被人类延用至今，“正”字计数法便是例证.研究地球的构造和历史的地质学家和观察人类的体质和社会特征的人类学家向我们提供了早期人的种

7、种遗迹，他们通过地层里各时期的堆积物的相对位置来估测远古至今各个时代的顺序，并以此来探索人类科学的起源丹皮尔著,李珩译.科学史及其与哲学与宗教的关系（第四版）[M].北京:商务出版社,1987..另一方面，研究科学思想史的科学家们则倾向于从自然科学最初形成的学科体系中寻觅人类科学思想史的根源，认为：“古代科学最先发展起来的是天文学与数学，其次是力学，此外还有一些生物学与医学方面的研究，因为这几个学科同古代人类的生产与生活