下载文档原格式
论可计算数及其在判定问题中的应用A.M.Turing 1．计算机2．定义自动机器计算机可循环数与不可循环数可计算的数列和数3．计算机的例子4．微型桌面更有深度的例子5．列举可计算的数列6．一般计算机7．一般计算机的详细描述8．对角线方法的应用9．可计算数的数组的例子10．一个大的可计算的数组的例子11．可计算数在其判定问题中的应用附录Endnotes：可计算的数可以简要描述为那些十进制形式可通过有限步骤来计算是实数。
虽然这篇论文表面上讲的是可计算数，但它也研究了可计算方程，无论整数、实数或可计算变量，等等。
这篇论文简单给出了可计算数、方程等之间的关系。
这会包括函数理论的发展和实变量用可计算数表示。
一个数，如果它是十进制形式，还可以被机器识别，它就是可计算的。
在9.10中给出了一些关于所有数都是可计算的的讨论。
其实，作者给出了一定大的数组都是可计算的。
它们包括，算术数学中的实数部分，Bessel函数中是实数部分的零，如x,e 等。
然而可计算数不全包括可定义是数，其中一个例子就是能找到一个不可计算却可定义的数。
即使可计算数组如此大，在许多方面它与实数集很相似。
从正确讨论的应用中，结论与Godel<1>的很相似，着都是有价值的证明。
在Alonzo Church的最近的一篇论文中介绍了“有效计算”的思想，它与作者“计数”的思想很接近，不过又定义的十分不同。
Church还探求了有关判定问题的结果。
有关“计数”和“有效计算”本质相同的证据，列在了附录中。
1．计算机我们知道可计算数是那些十进制可以通过有限步骤计算的，不过我们需要更明确的定义。
而计算机的需求是因为人类的记忆是有限的。
我们可以设想一个人将一个个实数输入一个只能存有限数q1，q2……qr的机器，将被叫做“m—配置”，这个机器被纸带供应，被分为“方格”（也叫做square），每次能生成一个符号。
某时只有一个方格叫做“r—th”，生成S(r)的符号。
计算机自从其诞生之日起，它的主要任务就是进行各种各样的科学计算。
文档处理，数据处理，图像处理，硬件设计，软件设计等等，都可以抽象为两大类：数值计算与非数值计算。
作为研究计算机科学技术的人员，我们大都对计算数学对整个计算机科学的重要性有一些了解。
但是数学对我们这些专业的研究和应用人员究竟有多大的用处呢？我们先来看一下下面的一个流程图：上图揭示了利用计算机解决科学计算的步骤，实际问题转换为程序，要经过一个对问题抽象的过程，建立起完善的数学模型，只有这样，我们才能建立一个设计良好的程序。
从中我们不难看出计算数学理论对用计算机解决问题的重要性。
下面我们将逐步展开对这个问题的讨论。
计算机科学的数学理论体系是相当庞杂的，笔者不敢随意划分，参考计算机科学理论的学科体系，我们谈及的问题主要涉及：数值计算，离散数学，数论，计算理论四大方向。
[一]数值计算（Numerical Computation）主要包括数值分析学、数学分析学、线性代数、计算几何学、概率论与数理统计学。
数值分析学又常被称为计算方法学，是计算理论数学非常重要的一个分支，主要研究数值型计算。
研究的内容中首先要谈谈数值计算的误差分析，误差是衡量我们的计算有效与否的标准，我们的算法解决问题如果在误差允许的范围内，则算法是有效的，否则就是一个无效的问题求解。
另外就是数值逼近，它研究关于如何使用容易数值计算的函数来近似地代替任意函数的方法与过程。
感觉应用比较广的不得不提切雪比夫逼近和平方逼近了。
笔者曾经尝试过的就是通过最佳平方逼近进行曲线的拟合，开发工具可以选择VC++或者Matlab。
插值函数是另外一个非常重要的方面，现代的计算机程序控制加工机械零件，根据设计可给出零件外形曲线的某些型值点，加工时走刀方向及步数，就要通过插值函数计算零件外形曲线及其他点函数值。
至于方程求根、线性方程组求解，一般的计算性程序设计问题都会多多少少的涉及一些，我们这里就不赘述了。
IV . 可计算函数4.1 理想计算机URMURM ——unlimited register machine理想计算机M ，有无穷多个寄存器 ,,,321R R R ，每个可存储一个任意大小的自然数，并记i R 中为 i r ，全部存储积存器的内容构成M 的一个内部状态即格局。
具体计算有限，只考虑前面有限个寄存器（格局）。
M 所能完成的四种指令：1. 清零指令Z(n)：将n R 的内容n r 清除掉，记为0:=n r2. 后继指令S(n)：将n R 的内容n r 增加1，记为1:+=n n r r3. 传送指令T(m,n)：把m R 的内容传送给n R ，其他单元不变，记为m n r r =:4. 条件转移指令（Jump ）J(m,n,q)：定义4.1 有穷指令的序列n I I I P 21=称为程序，程序中指令条数n 称为它的长度，指令编号称为它的编号。
若J(m,n,q)为第i 条指令，则n m r r =： M 执行指令q I n m r r ≠： M 执行指令1+i Iq > k （程序长度），m r = n r 时停机M 执行一条指令时完成两项工作： 1. 改变寄存器中某单元的内容； 2. 指出下一步执行哪一条指令记号： 1. ),,(21 a a P 程序P 在初始格局 ,,21a a 下的计算；2. ↓),,(21 a a P 计算最终停机；3.↑),,(21 a a P 计算不停机例4.1 程序1I ：Z （1） 2I ：S （1） 3I ：J （1，1，1） 对任何a ，均有↑)(a P定义4.2 令Z Z f n →: 上部分函数，其中Z 为自然数集。
1. 假定P 是程序，Z b a a a n ∈,,,,21 ，（1）计算),,,(21n a a a P 收敛（converge ）于b ，如果↓),,,(21n a a a P 并且在最终格局中b 在1R 中，记为b a a a P n ↓),,,(21（2）P URM-计算f ：如果Z b a a a n ∈∀,,,,21 ，b a a a P n ↓),,,(21 ，iff)(),,,(21f Dom a a a n ∈ ，并且b a a a f n =),,,(21 （特别，f 有定义时停机）2. 函数f 是URM-可计算的，如果存在程序URM-计算f 。
拟态计算与拟态安全Mimic Computing & Mimic Security邬江兴国家数字交换系统工程技术研究中心NDSC1传统计算机体系架构面临挑战图灵-哥德尔可计算性理论冯诺依曼体系结构当今计算机科学与工程的基础可计算性理论只揭示出图灵机可描述的东西是可计算的，不涉及计算速度和效率问题冯诺依曼结构导入存储程序方法解决了可计算理论中的自动化实现问题，并未关心计算速度和计算效率问题冯诺依曼哈佛流水线并行分布式计算机发展历程表明计算速度和效能的提高不仅可仰仗新型器件发明或性能的提升，更可以通过系统结构的创新改进获得速度竞赛CPU芯片架构发展正失去多样性活力Linpack-Game HPC体系架构发展趋向同质化计算能耗持续攀升困境TOP500/2014年(前三名)红杉Sequoi: 17.17PFlops 7.8MW 泰坦Titan:17.759Flops 8.2MW 天河2号TianHe-2：33.86Flops 17.8MW 预计E 级系统功耗可能达到TianHe-2：运转电费›1亿元/年天河2全速运转电费›1.5亿元/年超大规模并行化困境计算任务如何才能高度并行化？…when we start talking aboutparallelism and ease of use of trulyparallel computers, we're talking abouta problem that's as hard as any thatcomputer science has faced. …I would be panicked if I were in industry.Cited:“A Conversation with Hennessy &Patterson,”ACM Queue Magazine, 4:10, 1/07当我们谈论并行性和轻松地使用真正的并行计算机时，我们是在谈论一个计算机科学家面对的最困难的问题，如果我在计算机企业，我会感到恐慌…规模剧增陷入可用性骤降困境Sequoia 红杉:17.17PFlops Titan 泰坦: 17.59PFlopsTianHe-2天河2号: 33.68PFlops通用服务器集群构建的云计算/数据中心实际运行效率<35%计算效能提升的天花板计算速度与数据移动速率之间的矛盾（存储墙）用低阶计算模型、深度流水和超高主频的处理架构已逼近物理极限(Risc魔咒）计算资源颗粒度与高效使用的矛盾（功耗墙）并行算法的进步远远滞后并行处理核数增加速度（算法墙）创新计算架构发展“颠覆性”的结构技术开发新型器件忆阻器件、量子器件、深纳米、碳纳米管、石墨烯…功能等价条件下动态变结构计算愿景一个计算任务在不同阶段、不同时段、不同资源条件、不同服务质量要求等因素影响下，根据计算效能动态的生成（选择）合适的计算结构与环境为之服务结构适应应用2拟态计算Mimic Computing条纹章鱼（拟态章鱼）通过皮肤色素和头、腕、足、体的变化而改变色彩、纹理、外形和行为，从而获得摄食和防护的好处能拟态15种以上海洋生物，可在沙质海底和珊瑚礁环境完全隐身生物界拟态高手中国863计划十一五、十二五重大项目（2008—2013）“新概念高效能计算机体系结构及系统研究开发“拟态计算的实现特点 有一个包含N个异构计算环境模板的构造方案集合 能够根据运行参数实时选取构造方案集合 中合适的计算环境模板 有一个在结构粒度、结构层次、时间维度上 可重构的元结构多维动态重构（拟态化结构） 元结构按照环境模板动态生成实体计算环境拟态计算基本理念期望：计算、存储、互联等基础结构和 环境可变，逼近不同问题不同阶段 最优效能解 通用计算：MD-R追求不同服务、不同负载等状态下的 综合效能高的提升，构建最合适的处 理部件，形成最合适的体系结构结构确定、算法可变，能 够计算任何可计算问题CPU+ CPU+ Accelerator Accelerato r专用计算：MD-RMD-RHardware Hardware + ＋ Embedde Embedded d CPU CPU结构确定，算法确定， 处理负荷确定，高效解 决确定的应用问题CPU CPUHardwar Hardware e多维动态重构拟态化结构P: 粒度可变处理器级拟态重构P: 数量可变P:结构可变B1 B9 B2SHA1SHA1B32BC BC BC SHA1 BC SHA1BC B4 3 B5 4 35 2 4 2 BC 5 3 BC BC1 2 BC BC B5 3 2 3 5 BC 5 3 B5 BC 3 5 3 BC B6 22 BC 23 3 B7 BC 5 3BC1 B2B5 BC 3 BC1 2 B3 3BC BC BC BC 52 4 3 5 BC BC 5 5 3 BC 3 B7 B7 5 3 5 BC 5 BC 6 2 2 6 BC BC B8 B8 BC BC 5 2BC 3 3 5 2 7 7 BC 5 3 AESMD5 BC 5 3 5 BC 6 2 BC 7MD5B3MD5 B5B7 B8B7 B85 B1B BC1 2BC BC B3 B5 B B 5 2 3 C BC1 C BC1 BC 2 2 B5 5 3 3 B5B53BC MD5BC BC BC BC BC 5 23 5 2 3 5 2 2 3 BC BC BC B6 BC 2 BC 6 BC 2 BC 6 2 6 2 B 23 5 2 BC 3 5 2BC BC B8 BC7 B7 B7 B8 BC7 C B8 BC7 7 7 7 4 4 4 4 BC BC 2 BC BC BC 5 3 5 3 B9 9 9 9 BC BC BC BC BC BC BC BC BC B4 B9 5 4 59 4 59 4 9SHA1SHA1B3 2SHA1 BC B4 B5 3 2BC 4BC BC 35 2 B5 BC 3 5 3 B6 2BC 4BC 5 BC 5 B7 5 BC 6 2 BC 5 B7 5 BC 6 2 B8 BC 7 B8B8 B5 3 B1 BC1 B2 BC1 BC2 B3 B5 3 2 BC 5 BC2 BC 333 B7 53BC9 B5 BC2 5BC9 BC5 B12 BC2 5B5BC9 4 BC1 BC5 B12 5 3 4 BC2BC AES BC 5 4 5 4 BC1 BC1 BC5 B9BC5 B5 BC 2 5 BC 2 16 16 13 4 13 4BC 5 4 B9BC5 BC 16 13 4AES B9BC5 16AES B2 B9BC 2BC 2 B CBC 19 0 B5 B C 1 1BC 2 BCB1 BCB1BC BC BC BCBCBC BCBC B8 B8 B7 5 0 7 1 5 10 7 11 5 10 7 11 B B B B C BC C C C RC RC 1 9 1 1 1 4 4 0 1 0 1 BC 10 BC B8 11 RC 4 B8 B5 RC 43BC BC 5 3 2 3 B7BC B8 5 2 BC 7B9B B BC 1 1 9 0 13BC 53BC 53多维动态重构拟态化结构M: 种类和容量可变SRAM DDR存储器级拟态重构SSD Disk Array Net StorageDISKTapeM:结构可变 /内容可计算Stack FIFORAM0 1 2 3 4 51 1 1 1 1 10 0 0 0 0 01 1 1 0 1 1 1 1 1 1 1 0 CAM0 0 0 1 0 01 1 1 0 * *1 0 1 0 * 11 1 * 0 * 1M:编址、访存方式可变1 1 111 分段编址、统一编址2 1233多维动态重构（拟态化结构）互连网络级拟态重构C:互连拓扑可变 C:互连协议可变C:互连带宽可变 C:传输内容可处理（变速箱）通用构件 专用构件 可重构构件结构动态生成(数控加工中心)用三种典型应用进行了原理验证 Web服务(输入输出密集)N-body（计算密集）图像识别(存储密集)三种典型应用500余种场景第三方权威测试：（参照IBM 2013年款高端服务器）三种典型应用效能比提升倍数在13.6-315倍3拟态安全防御Mimic Security Defense现行的基于威胁防范的防御体系CPU 自主可控硬件自主操作系统服务与应用BLP WPDRRCP 2DR Chine se Wall PDRR Biba 安全模型密码技术入侵检测技术防火墙技术入侵防护技术网络诱骗技术应急响应技术安全技术量子混沌DNA神经网络分组序列公钥哈希特征匹配状态分析机器学习数据挖掘包过滤代理防火墙HIPS 主机行为分析与阻断NIPS 网络流量与异蜜罐密网，攻击信息采集分析CERT PDCERF威胁防御体系不能提供风险控制能力CPU 自主可控硬件自主操作系统服务与应用BLP WPDRRCP 2DR Chine se Wall PDRR Biba 安全模型密码技术入侵检测技术防火墙技术入侵防护技术网络诱骗技术应急响应技术安全技术量子混沌DNA神经网络分组序列公钥哈希特征匹配状态分析机器学习数据挖掘包过滤代理防火墙HIPS 主机行为分析与阻断NIPS 网络流量与异蜜罐密网，攻击信息采集分析CERT PDCERF实现威胁防范到风险控制的转变未知漏洞和后门主动开放的商业环境下系统架构技术生物免疫学1 : 10人体细胞：细菌病毒八卦阵八卦阵靠散布成八，复而合一，分合变化，可以组成六十四阵。
第36卷 第4期2009年4月计算机科学Comp uter Science Vol.36No.4Apr.2009到稿日期:2008210230 朱亚宗(1944-),男,博导,主要研究方向为科学方法论、科学思想史等。
本文为2008年全国“计算思维与计算机导论”专题学术研讨会的特邀论文。
论计算思维———计算思维的科学定位、基本原理及创新路径朱亚宗(国防科技大学人文社科学院 长沙410073)摘 要 指出计算思维、实验思维与理论思维是人类三大科学思维方式,并初步梳理出可计算性原理、形理算一体原理与计算机设计原理等三大计算机基本原理。
还指出,交叉创新是计算思维创新发展的根本途径。
关键词 计算思维,科学思维,计算机原理,交叉创新中图法分类号 TP520 文献标识码 A Computational Thinking :its Scientif ic Position ,B asic Principles and Innovation MethodsZHU Ya 2zong(School of Humanities and Social Science ,National University of Defense Technology ,Changsha 410073,China )Abstract The paper firstly proposesd that computational thinking ,experimental thinking and theoretical thinking are three kinds of scientific human thinking ,thus gradually concluding three basic principles of computer ,i.e.,the calcula 2bility principle ,the integration of form 2theory 2calculation principle and the computer design principle.The paper finally pointed out that cross innovation is the prime way of developing computational thinking.K eyw ords Computational thinking ,Scientific thinking ,Computer principles ,Cross innovation 计算是人类文明最古老而又最时新的成就之一。
《计算理论》复习题总结《计算理论》复习题总结1、⾃动机、可计算性、复杂性内涵及关系；计算理论的三个传统的核⼼领域：⾃动机、可计算性和复杂性。
通过“计算机的基本能⼒和局限性是什么？“这⼀问题将这三个领域联系在⼀起。
可计算理论与复杂性理论是密切相关的，在复杂性理论中，⽬标是把问题分成容易计算的和难计算的；⽽在可计算理论中，是把问题分成可解的和不可解。
⾃动机阐述了计算的数学模型的定义和性质，主要包含两种模型：有穷⾃动机模型；上下⽂⽆关⽂法模型。
可计算性理论和复杂性理论需要对计算机给了⼀个准确的定义。
⾃动机理论允许在介绍与计算机科学的其他⾮理论领域有关的概念时使⽤计算的形式化定义。
2、有穷⾃动机、正则语⾔、正则表达式、⾮确定有穷⾃动机、⾮正则语⾔；有穷⾃动机：描述能⼒和资源极其有限的计算机模型。
是⼀个5元组（Q，∑，δ，q0,F），其中1）Q是⼀个有穷集合，称为状态集。
2）∑是⼀个有穷集合，称为字母表。
3）δ：Q×∑→Q是转移函数。
4）q0∈Q是起始状态。
5）F?Q是接受状态集。
正则语⾔：如果⼀个语⾔能被有穷⾃动机识别。
正则表达式：⽤正则运算符构造描述语⾔的表达式。
称R是正则表达式，如果R是：1）a，a是字母表中的⼀个元素；2）ε；3）?;4）（R1?R2）；5）(R1 R2)；6）(R1*)⾮确定有穷⾃动机：是⼀个5元组（Q，∑，δ，q0,F），其中1）Q是有穷状态集。
2）∑是有穷字母表。
3）δ：Q×∑ε→P（Q）是转移函数。
4）q0∈Q是起始状态。
5）F?Q是接受状态集。
3、上下⽂⽆关语⾔及上下⽂⽆关⽂法、歧义性、乔姆斯基范式、下推⾃动机、等价性、⾮上下⽂⽆关语⾔；上下⽂⽆关语⾔：⽤上下⽂⽆关⽂法⽣成的语⾔。
上下⽂⽆关⽂法：是⼀个4元组（V，∑，R，S）且1）V是⼀个有穷集合，称为变元集2）∑是⼀个与V不相交的有穷集合，称为终结符集3）R是⼀个有穷规则集，每条规则由⼀个变元和⼀个由变元及终结符组成的字符串构成，4）S∈V是起始变元歧义性：如果字符串W在上下⽂⽆关⽂法G中有两个或者两上以上不同的最左派⽣，则称G歧义地产⽣的字符串W。
