当前位置：文档之家 › 第2章可计算性理论基础

第2章可计算性理论基础

  • 格式：doc
  • 大小：1.32 MB
  • 文档页数：21

1 第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, Vol.32(1).

② 董荣胜, 古天龙. 计算机科学技术与方法论 [M]. 北京: 人民邮电出版社, 2002.

③ 郝宁湘. 计算: 一个新的哲学范畴. 哲学动态 [J]. 2000年第11期.

④ 李啸虎, 田廷彦, 马丁玲. 力量—改变人类文明的50大科学定理[M]. 上海: 上海文化出版社, 2005.

2 一种特殊的本领，这就是把直观的形象变成抽象的数字，进行抽象思维活动. 正是由于能够在“象”和“数”之间互相转换，人类才真正具备了认识世界的能力. 从“计数”到“数”的概念形成，是人类在抽象思维领域中迈出的辉煌一步.

考古发现最早人类留有计数痕迹的东西是一些带有刻痕的骨头，这些骨头出土于欧洲西部，距今已有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 London

Mathematical Society [J]. 1936-1937(45-46): 230-256, 544-546.

3 可计算函数，以及基于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世纪

合集下载

2013计算理论复习题

2013计算理论复习题

《计算理论》复习题

1、设语言A=｛w | w含有子串0101，即对某个x和y，w=x0101y｝，字母表为{0，1}

a. 画出识别A的DFA的状态图。

b. 画出识别A的NFA的状态图（规定状态数为5）。

2、把下图的有穷自动机转换成正则表达式。

3、设语言A={www | w∈{a,b}*}，利用泵引理证明A不是正则语言。

4、证明在3.1节开始部分给出的文法G2中，字符串the girl touches the boy with the flower 有两个不同的最左派生，叙述这句话的两个不同的意思。

5、有自动机M，接受语言L={WcWR | W∈{a,b}*∪c}，请给出这台PDA的形式定义、状态图，并非形式地描述它的运行。

6、设语言A={0n1n0n1n | n≧0}，利用泵引理证明A不是上下文无关的。

7、设语言A={w | w至少含有3个1}，字母表为{0，1}

a. 给出产生语言A的上下文无关文法。

b. 给出产生语言A的下推自动机的非形式描述和状态图。

8、检查图灵机的形式定义，回答下列问题并解释你的推理：

a. 图灵机能在它的带子上写下空白字符吗？

b. 图灵机能只包含一个状态吗？

9、证明正则语言类在并运算下封闭。

10、设INFINITEDFA={|A是一个DFA，且L(A)是一个无限语言}。证明INFINITEDFA是可判定的。

11、设B是{0，1}上所有无限序列的集合，用对角化方法证明B是不可数的。

12、设EQCFG={|G和H都是一个CFG，且L(A)= L(B)}，证明EQCFG是不可判定的。

13、证明：如果A是图灵可识别的，且A≤mA，则A是可判定的。

14、证明所有的图灵可识别问题都映射可归约到ATM。

b a

b 1 2 a

可计算性理论

可计算性理论

可计算性理论

1 计算性理论介绍

计算性理论，也称为计算机科学理论，是一个抽象的数学学科。

这一理论研究计算机及其基本操作及其基础，包括计算过程、计算设

备、数学建模、算法设计、程序设计、机器翻译、人工智能等。 除此

以外，计算性理论还包括一些共同的范畴，如数学逻辑、图灵机理论

和计算语言。

2 计算性理论的应用

计算性理论的最常见的应用之一是计算机编程，利用它可以设计

计算机程序来完成特定的任务。此外，该理论也被用于设计和实现智

能型计算机系统，如自动驾驶系统、操作系统、游戏系统，以及难事

务流水线。计算性理论还可用于社会科学，如模拟各种社会现象，例

如股票价格波动以及市场营销研究。

3 计算性理论的未来

未来，随着人工智能技术的演变，计算性理论也会发生很大的变

化。随着模拟和计算能力的不断改善，将有望设计出一些在计算效率

上比现有技术更先进的方法，使用这些技术可以处理更复杂的任务。

此外，可以运用计算性理论来实现高速及高效的信息处理，它将能够

帮助我们解决复杂的社会问题，从而实现最全面的发展。

可靠性理论基础复习资料

可靠性理论基础复习资料

可靠性理论基础复习资料

目 录

第一章绪论

第二章可靠性特征量

第三章简单不可修系统可靠性分析

第四章复杂不可修系统可靠性分析

第五章故障树分析法

第六章三态系统可靠性分析

第七章可靠性预计与分配

第八章寿命试验及其数据分析

第九章马尔可夫型可修系统的可靠性

第一章：可靠性特征量

2.1可靠度

2.2失效特征量

2.3可靠性寿命特征

2.4失效率曲线

2.5常用概率分布

2.1可靠度

一、 系统的分类：可修系统与不可修系统；

可修系统是指系统的组成单元发生故障后，经过维修能够使系统恢复到正常工作状态。 不可修系统是指系统或其组成单元一旦发生失效，不在修复，系统处于报废状态。

二、 可靠性定义

产品在规定条件下，规定时间内，完成规定功能的能力。

1. 产品：可以是一个小零件，也可以指一个大系统。

2. 规定条件：主要是指使用条件和环境条件。

3. 规定时间：包括产品的运行时间、飞机起落架的起飞着陆次数、循环次数或旋转次数等。 产品可靠性是非确定性的，并且具有概率性质和随机性质。

广义可靠性与狭义可靠性

指可修复产品在使用中或者不发生故障(通过预防性维修)，或者发生故障也易于维修，因而经常处于可用状态 的能力。

广义可靠性=狭义可靠性+可维修性

广义可靠性典型事例：赛车

可靠性的分类：固有可靠性和使用可靠性

固有可靠性：通过设计、制造、管理等所形成的可靠性

(通常体现在产品的固有寿命上)

使用可靠性：产品在使用条件影响下，保证固有可靠性的发挥与实现的功能。

(通常体现在产品的实际使用寿命上)

使用条件：包括运输、保管、维修、操作和环境条件等。

例1:判断下面说法的正确性：

所谓产品的失效，即产品丧失规定的功能。对于可修复系统，失效也称为故障。 (V)

例2：可靠度R(t)具备以下那些性质？ ( BCD) A. R(t)为时间的递增函数 B. ow R(t) < 1

C. R(0)=1 D. R()=0

第2章 现代贸易理论的基础

第2章 现代贸易理论的基础

现代贸易理论试图回答如问题：

(1)贸易基础(basis for trade)由什么构成--即国与国之间为什么要进和出口某些商品?

(2)商品在世界市场按什么样的贸易条件(terms of trade)(相对价格)进行交换?

(3)从生产和消费方面来看，国际贸易收益(gains from internationa1 trade)是什么?本章将首先毓要回顾现代贸易理论的发展历史，然后介绍分析国际贸易影响时用到的理论工具，进而探讨这些问题。

现代贸易理论的发展历史

现代贸易理论是经济思想进化的产物。重商主义以及后来的亚当·斯密和人卫·李嘉图的著作都为现代贸易理论提供了框架。

重商主义

在1500-1800年间，欧洲出现了一批关注国家建设的学者。按照重商主义(mercantists)的观点，一个吲家如何管理它的国内和国际事务以提高自身的利益，是建设国家的中心问题，而拥有一个强大的对外贸易部门则是该问题的答案。如果一个国家能够实现贸易顺差(出口超过进口的剩余)，就可以得到世界其他国家支付的黄金和白银。这种收入将增加消费，提高国内的产出和就业水平。为了促成贸易顺差，重商主义学派主张政府进行贸易管制，并建议采用关税、配额和其他商业政策将进口限制在最低水平，以保护一个国家的贸易地位。。

进入18世纪，重商主义的经济政策受到了强烈的攻击。根据大卫·休谟的价格流转学说(price-specie-口ow doctrine)，贸易顺差只可能是短期的，会随着时间的推移自动消除。为说明这一点，假定英国获得了贸易盈余，导致黄金和白银流入。由于这些贵金属构成了英国货币供给的一部分，它们的流入会增加流通中的货币数量，从而使得英国的物价水平相对于其贸易伙伴的而言比较高。物价水平的上升会激励英国居民购买外国生产的商品，同时英国的出口额会降低。结果是，该国的贸易盈余最终将自动消除。休谟的价格流转机制表明，重商主义的政策最多只能带来短期的经济优势。