一个开始状态和一个结束状态.doc

《一个开始状态和一个结束状态.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、一个开始状态和一个结束状态讨论这个十分重要的不可计算性和不可判定性问题就像告诫人们三等分角不可能一样，这方面的研究成果可使人们避免无效的劳动与此相关的问题是形式系统的一致性和完备性问题，这在九中织讨总之，八、九两说的是现实世界计算能力的极限计算模型的计算能力还受着另一个固家的限制，那就是计算的复杂性通俗地说，可称之为计算的繁复程度对此，人们首先想到的是计算所需的步数，但这只是复杂性的一种，称为时间复杂性通常用计算所得的各种开销之大小衡量计算复杂性，时间是一种开销，空间可想象为算翅用的草稿纸也是一种开销，还可以定义其它的开销十彦研究抽柬计算模型的计算复杂性

2、，十一研究具体的算法类中校认为员难的一类完备类的复杂性，这西方面都已有权丰富的研究成果有关计算的另一个大问题是计算的语义问题通俗地讲即是怎样保证计算的结果是我们所需0.68uF35VB要的即如果一个算法用两种形式表示出来，一种是说明性的例如求两个数的最大公约数，另种是道程性的例如欧儿里镕辗转相除法，如何才能判断过程性的算法达到了说明性算法的要求计算的语义问题是一个极大的问题。只能在最后一触及它的很小一点皮毛，供读者品味二图灵机跳不出的如来佛手心计算的能行性和可构造性研究的员著名产物，也许是因灵机厂图灵是一位英国数学家，生于年月日，卒于年月日，只活了岁，然

3、而却在数学和计算理论方面作出了卓越的贡献他在年发表的关于可计算的数及其对判定问题的应用一文中提出了一个非常重要的关于计算的数学模型，后世称之为图灵机其重要性在于这是一个朗行的计算模型，它的原理非常之简单然而却能计算一切能行可计算的问题类，因此它的功能不会弱于任何其它的能行计算模型当然，这个结VISHAG钽电容论从未杖严格证明过，而且，它是证明不了的因为图灵机是一个严格的数学模型，而所谓可汁算的问题类则是一个用语言描述的模糊概念我们只能证明一个精确的数学概念等价干另一个精确的数学概念，却无法证明一个模糊的概念等价于一个精确的概念不过。从图灵机创立以来伪无数

4、事实使人们相信这一点是对的还从未有人发现过一个为图灵机计算不了的问题类，就侄孙悟空跳不出如来佛的手心一样现在，数学家们不但不怀疑这一点，而且把图灵机可计算作为能行可汁算的代名词各种各样的关于计算的数学模型，均以能被证明和图灵机等价作为它们具有最高计算能力的标东图灵的论文发表不到十年，现实的电子计算机就间世了计算机科学家们公认图灵酌思想为电子计算机的诞生奠定了理论基础，固灵因此而获得了一项殊荣，目前国际上授予计算机科学家的最高学术成就奖就是以他的名字命名的。所以，一切对计算的数学理论感兴越的人都应该认识和了解瞧机图灵机的计算在一条带子上进行，这条带子在两个

5、方向均功无穷长可以把它想象成解析几何中的轴带子上划分为无穷多个格可以把它想象为轴上长度为的区间带子上方有一个沿带子方向来回移动的读写头读写头和带子的关系有点象录音机中磁头和磁带的关系计算通过读写头的移动和谈写来完成为了控制读写头的这些操作，每个图灵机有一个状态集沁，其中包括一个开始状态和一个结束状态它还有一组符号沁，其中包括一个空白符号。cjmc%ddz