丘奇-图灵论点与人类认知能力和极限

理解计算郝宁湘随着计算机日益广泛而深刻的运用，计算这个原本专门的数学概念已经泛化到了人类的整个知识领域，并上升为一种极为普适的科学概念和哲学概念，成为人们认识事物、研究问题的一种新视角、新观念和新方法。

什么是计算与计算的类型在大众的意识里，计算首先指的就是数的加减乘除，其次则为方程的求解、函数的微分积分等；懂的多一点的人知道，计算在本质上还包括定理的证明推导。

可以说，“计算”是一个无人不知元人不晓的数学概念，但是，真正能够回答计算的本质是什么的人恐怕不多。

事实上，直到1930年代，由于哥德尔（K.Godel，1906-1978）、丘奇(A.Church，1903-1995)、图灵(A.M.TUI-ing，1912-1954)等数学家的工作，人们才弄清楚什么是计算的本质，以及什么是可计算的、什么是不可计算的等根本性问题。

抽象地说，所谓计算，就是从一个符号串f变换成另一个符号串g。

比如说,从符号串12+3变换成15就是一个加法计算。

如果符号串f 是，而符号串g是2x,从f到g的计算就是微分。

定理证明也是如此，令f表示一组公理和推导规则，令g是一个定理,那么从f到g的一系列变换就是定理g的证明。

从这个角度看，文字翻译也是计算，如f代表一个英文句子，而g为含意相同的中文句子，那么从f到g就是把英文翻译成中文。

这些变换间有什么共同点？为什么把它们都叫做计算？因为它们都是从己知符号(串)开始，一步一步地改变符号(串)，经过有限步骤，最后得到一个满足预先规定的符号(串)的变换过程。

从类型上讲，计算主要有两大类：数值计算和符号推导。

数值计算包括实数和函数的加减乘除、幕运算、开方运算、方程的求解等。

符号推导包括代数与各种函数的恒等式、不等式的证明,几何命题的证明等。

但无论是数值计算还是符号推导,它们在本质上是等价的、一致的，即二者是密切关联的，可以相互转化，具有共同的计算本质。

随着数学的不断发展,还可能出现新的计算类型。

10大悖论1. 邱奇-图灵悖论邱奇-图灵悖论源自数理逻辑中的一个重要命题：不可能存在一个算法，能够判断任意算法是否停机。

这个命题的证明过程非常复杂，但其结论却具有深刻的哲学意义。

在计算机科学中，图灵机是一种抽象的计算模型，被认为是现代计算机的理论基础。

邱奇和图灵分别独立提出了图灵机的概念，并证明了它的等价性。

然而，他们的工作也揭示出了一个无法解决的问题：无法判断一个算法是否会停机。

这意味着，即使我们拥有了最强大的计算机和最聪明的算法，我们仍然无法预测一个算法是否会在有限的时间内停止运行。

这个悖论挑战了我们对计算机科学的基本认识，也引发了对人工智能和机器学习领域的深思。

2. 赫胥黎悖论赫胥黎悖论是关于集合论的一个重要悖论。

在集合论中，我们通常认为一个集合是由它的成员所确定的。

然而，赫胥黎悖论却质疑了这一观点。

考虑一个由所有不包含自己的集合组成的集合。

根据我们的直觉，这个集合应该是一个合法的集合。

然而，如果我们问这个集合是否包含自己，我们会发现一个悖论：如果这个集合包含自己，那么根据定义，它不应该包含自己；如果这个集合不包含自己，那么根据定义，它应该包含自己。

这个悖论揭示了我们对集合的理解存在一些隐含的问题，也引发了对集合论基础的深入思考。

3. 费尔马定理悖论费尔马定理是数学中一个著名的未解之谜。

它声称没有正整数解的方程x^n + y^n = z^n，其中n大于2。

然而，费尔马定理悖论在于，虽然费尔马定理已经被证明是正确的，但其证明过程却非常复杂，以至于无法在有限时间内完成。

这个悖论引发了对数学证明的思考：我们如何确定一个命题是否为真？费尔马定理悖论表明，即使我们相信一个命题是真的，我们也可能无法证明它。

这对于数学和逻辑的发展产生了重要影响。

4. 佩亚诺悖论佩亚诺悖论源自数学中的一个基本问题：是否存在一个能够判断所有数学命题真假的公理系统？佩亚诺悖论证明了这是不可能的。

如果我们假设存在这样一个公理系统，那么我们可以构造一个命题：这个命题在公理系统中是不可证明的，但它却是真的。

计算机科学家应具备的基本素质：1.良好的家庭教育（或极强的自学能力）其祖父曾获得剑桥大学数学荣誉学位，但他父亲的数学才能平平。

因此，图灵的家庭教育，对他以后在数学及计算机方面的成就并没有多少帮助。

在他42年的人生历程中，他的创造力是丰富多彩的，他是天才的数学家和计算机理论专家。

3岁时，小图灵就进行了他的首次实验，尝试把一个玩具木头人的小胳膊、小腿掰下来栽到花园里，等待长出更多的木头人。

到了8岁，他更开始尝试写一部科学著作，题目为《关于一种显微镜》。

16岁就开始研究爱因斯坦的相对论。

24岁提出图灵机理论，31岁参与COLOSSUS 的研制，33岁设想仿真系统，35岁提出自动程序设计概念，38岁设计“图灵测验”。

2.敏锐的观察能力种木头人；他还有个经常掉链子的自行车，要换作常人肯定第一时间就修好了。

图灵不是常人，他每次骑车时会默默计数，终于发现每蹬12圈就会掉一次链子。

从此，他每蹬到第12圈就迅速往回倒一下，后来干脆做了个机械计数装置，每到12圈就自动倒轮。

就连和小朋友们玩足球，他也能放弃当前锋进球这样出风头的事，只喜欢在场外巡边，因为这样能有机会去计算球飞出边界的角度。

3.渊博的知识他短暂的生涯中，图灵在量子力学、数理逻辑、生物学、化学方面都有深入的研究，在晚年还开创了一门新学科——非线性力学。

在校期间，图灵还是现代语言哲学大师维特根斯坦班上最出色的学生。

他对由剑桥大学的罗素和怀特海创立的数理逻辑很感兴趣。

1953年-1954年，继续在生物和物理学等方面的研究。

4.持之以恒的身体锻炼和保护图灵对花粉过敏，每年春天喷嚏不止。

当时有一种抗过敏药，不知谁告诉他说此药对大脑有副作用。

图灵一听立即把药给扔了，此后出门都得携带防毒面具。

图灵还是一位世界级的长跑运动员。

他的马拉松最好成绩是2小时46分3秒，比1948年奥林匹克运动会金牌成绩慢11分钟。

1948年的一次跨国赛跑比赛中，他赢了同年奥运会银牌得主。

1954年6月8日，图灵42岁，正逢进入他生命中最辉煌的创造顶峰却永远的走了。

人工智能：模型与算法_浙江大学中国大学mooc课后章节答案期末考试题库2023年1.下面哪个描述不属于邱奇－图灵论题所包含的意思（）参考答案:任何表达力足够强的(递归可枚举)形式系统同时满足一致性和完备性2.在本课程内容范围内，“在状态s，按照某个策略采取动作a后在未来所获得反馈值的期望”，这句话描述了状态s的（ )参考答案:动作-价值函数3.德国著名数学家希尔伯特在1900年举办的国际数学家大会中所提出的“算术公理的相容性(the compatibility of the arithmetical axioms)”这一问题推动了可计算思想研究的深入。

在希尔伯特所提出的这个问题中，一个算术公理系统是相容的需要满足三个特点。

下面哪个描述不属于这三个特点之一（）参考答案:复杂性，即算法性能与输入数据大小相关4.下面哪句话描述了现有深度学习这一种人工智能方法的特点（）参考答案:大数据，小任务5.下面哪个说法是不正确的（）参考答案:一个有向无环图无法唯一地决定一个联合分布6.下面哪句话语较为恰当刻画了监督学习方法中生成方法的特点（）参考答案:授之于鱼、不如授之于“渔”7.假设原始数据个数为n，原始数据维数为d，降维后的维数为l，下面对主成分分析算法描述不正确的是（）参考答案:主成分分析学习得到了l个d维大小的向量，这l个d维向量之间彼此相关8.逻辑斯蒂回归和线性区别分析均可完成分类任务，下面描述正确的是（）参考答案:逻辑斯蒂回归可直接在数据原始空间进行分类，线性区别分析需要在降维所得空间中进行分类9.下面对逻辑斯蒂回归（logistic regression)和多项逻辑斯蒂回归模型(multi-nominal logistic model)描述不正确的是（）参考答案:逻辑斯帝回归是监督学习，多项逻辑斯蒂回归模型是非监督学习10.在神经网络学习中，每个神经元会完成若干功能，下面哪个功能不是神经元所能够完成的功能（）参考答案:向前序相邻神经元反馈加权累加信息11.下面对前馈神经网络描述不正确的是（）参考答案:同一层内神经元之间存在全连接12.下面对感知机网络（Perceptron Networks）描述不正确的是（）参考答案:感知机网络具有一层隐藏层13.下面对梯度下降方法描述不正确的是（）参考答案:梯度方向是函数值下降最快方向14.我们可以将深度学习看成一种端到端的学习方法，这里的端到端指的是（）参考答案:输入端-输出端15.在前馈神经网络中，误差后向传播（BP算法）将误差从输出端向输入端进行传输的过程中，算法会调整前馈神经网络的什么参数（）参考答案:相邻层神经元和神经元之间的连接权重16.前馈神经网络通过误差后向传播（BP算法）进行参数学习，这是一种（）机器学习手段参考答案:监督学习17.下面对前馈神经网络这种深度学习方法描述不正确的是（）参考答案:隐藏层数目大小对学习性能影响不大18.下面对浅层学习和深度学习描述不正确的是（）参考答案:浅层学习仅能实现线性映射、深度学习可以实现非线性映射19.卷积操作是卷积神经网络所具备的一个重要功能，对一幅图像进行高斯卷积操作的作用是（）参考答案:对图像进行平滑（模糊化）20.对完成特定任务的卷积神经网络训练采用的是监督学习方法。

丘奇-图灵论题、超计算和人工智能如果我们认可丘奇-图灵论题和相似性原则，那么人就是图灵机。

所有目前的人工智能工作都是建立在这个认同之上的。

丘奇-图灵论题和洪加威相似性原则是战斗在第一线的研究者的工作假设。

丘奇-图灵论题说的是能行性（effectiveness），而相似性原则则是说的效率（efficiency）。

多依奇在他的科普著作里提到，他认为人类有史以来有4个伟大理论：达尔文进化论、波普尔证伪理论、量子理论和计算理论。

他的工作把量子理论和计算理论整合到一起。

但他不认为人脑是量子计算机，这点有别于彭罗斯。

自然科学和唯物论、经验论的关系要比唯心论、理性论的关系更近，背后都有一条归约主义路线图（reductionist），从生物到化学，再到物理。

一个有机体最终被归约到物理化学过程，一个活的、有意识的生物最终会被归约到神经网络过程。

这是自顶向下的思路。

近来也有自底向上的思路，例如细胞自动机，利用很简单的几条规则，就可展示很复杂的行为。

沃尔夫勒姆在他的《新科学》（A New Kind of Science ）一书中提到的这种现象其实早就被数学家康韦（John Conway）观察到，他设计了《生命游戏》（Game of Life ），企图利用细胞自动机来说明确定性和自由意志的问题。

高德纳在评论康韦的工作时说：所有规则都是确定性的，但游戏的演进过程却给人一种自主性的感觉。

高老喜欢阅读英国女作家塞耶斯（Dorothy Sayers），她更偏爱写剧本而不是小说，她说剧本给了演员发挥再创作的机会，这个再创作就是自由意志。

高老说量子力学为自由意志提供了空间，也使得上帝可以操纵世界而不违反物理定律。

所谓“太阳底下没啥是新鲜的”，但几条简单规则展示的行为却无法解释。

如果考虑数学定理证明，我们可以说勾股定理不新鲜——毕竟从简单几何公理不用费太大力气就可证明。

但我们敢说黎曼猜想也不新鲜或者庞加莱猜想的证明也不新鲜因为所有结果不都是可以从起始点（那几条数论公理）推出吗？这似乎模糊了柏拉图主义（实在论）和构造主义的边界。

个人收集整理-ZQ图灵在计算机理论方面地贡献：1.提出计算机地概念年，图灵恢复在理论计算机科学方面地研究，并结合战时地工作，具体研制出新地计算机来.同年，图灵开始从事“自动计算机”()地逻辑设计和具体研制工作.年制出了样机，年制成大型机.2.把可计算函数定义为图灵机可计算函数．年，图灵在他地“可计算性与λ可定义性”一文中证明了图灵机可计算函数与λ可定义函数是等价地，得出：算法(能行)可计算函数等同于一般递归函数或λ可定义函数或图灵机可计算函数．这就是“丘奇图灵论点”，相当完善地解决了可计算函数地精确定义问题，对数理逻辑地发展起了巨大地推动作用.3.开创了“自动机”这一学科分支，促进了电子计算机地研制工作．4.提出了通用图灵机地概念它相当于通用计算机地解释程序，这一点直接促进了后来通用计算机地设计和研制工作，在给出通用图灵机地同时，图灵就指出，通用图灵机在计算时，其“机械性地复杂性”是有临界限度地，超过这一限度，就要靠增加程序地长度和存贮量来解决．这种思想开启了后来计算机科学中计算复杂性理论地先河.5.解决了著名地希尔伯特判定问题狭谓词演算公式地可满足性地判定问题.他用一阶逻辑中地公式对图灵机进行编码，再由图灵机停机问题地不可判定性推出一阶逻辑地不可判定性.他在此处创用地“编码法”成为后来人们证明一阶逻辑地公式类地不可判定性地主要方法之一.6.图灵测试年，图灵发表论文阐述存储程序计算机地设计.图灵地自动计算机与诺伊曼地离散变量自动电子计算机都采用了二进制，都以“内存储存程序以运行计算机”打破了那个时代地旧有概念.7.人工智能人工智能致力研发运行型号储存程序式计算机所需地软件.年他发表论文《计算机器与智能》，为后来地人工智能科学提供了开创性地构思.提出著名地“图灵测试”，指出如果第三者无法辨别人类与人工智能机器反应地差别，则可以论断该机器具备人工智能.1 / 1。

Text A I. Complete the following sentences according to the information in the text.1. programmable, analog, digital2. continuous, discrete3. billing, shipping, receiving, inventory control4. computations, MPU, CPU5. Complex Instruction Set Computer6. Digital Signal Processing7. integer, logic8. buses, pulses,9. Random Access Memory, internal10. keyboards, mouse, monitors, printersII. Translate the following terms and phrases into Chinese.1.external devices 1.外部设备2.output device 2.输出设备3.parallel device 3.并行设备4.assembly language 4.汇编语言5.block device 5.块设备6.floating point 6.浮点7.data stream7.数据流8.input device8.输入设备9.integrated circuit9.集成电路10 .main storage10.主存III. Translate the following terms and phrases into English.缩写完整形式中文意义1.ALU Arithmetic/Logic Unit运算器2.CPU Central Processing Unit或Central Processor Unit中央处理器3.CISC Complex Instruction SetComputer 复杂指令集计算机4.DSP Digital Signal Processing数字信号处理5.EPROM Erasable Programmable ReadOnly Memory 可擦可编程只读存储器6.LED light-emitting diode发光二级管7.MODEMMOdulator, DEModulator调制解调器8.RAM Random Access Memory随机访问存储器9.ROM Read Only Memory只读存储器10 .RISC Reduced Instruction SetComputer精简指令集计算机IV. Fill in the gaps with the words or phrases chosen from the box. Change the forms where necessary.1. instructions 2. devices 3. concept 4. consuming 5. integrated circuits6. space7. fit into8. Information Age9. embedded computer 10. controlV. Translate the following passage into Chinese.计算机能够储存和执行被叫做程序的许多指令，这使其非常通用并不同于计算器。

⼈⼯智能机器⼈之⽗：艾伦·图灵⼈⼯智能之⽗：艾伦.图灵⼈⼯智能之⽗：图灵提出计算机理论可与⽜顿⽐肩图灵艾伦·麦席森·图灵（Alan Mathison Turing，1912年6⽉23⽇－1954年6⽉7⽇），英国数学家、逻辑学家，被称为计算机之⽗，⼈⼯智能之⽗。

1931年图灵进⼊剑桥⼤学国王学院，毕业后到美国普林斯顿⼤学攻读博⼠学位，⼆战爆发后回到剑桥，后曾协助军⽅破解德国的著名密码系统Enigma，帮助盟军取得了⼆战的胜利。

2013年12⽉24⽇，在英国司法部长克⾥斯·格雷灵（Chris Grayling）的要求下，英国⼥王向图灵颁发了皇家赦免。

英国司法部长宣布，“图灵的晚年⽣活因为其同性取向⽽被迫蒙上了⼀层阴影，我们认为当时的判决是不公的，这种歧视现象现在也已经遭到了废除。

为此，⼥王决定为这位伟⼈送上赦免，以此向其致敬。

” 图灵对于⼈⼯智能的发展有诸多贡献，提出了⼀种⽤于判定机器是否具有智能的试验⽅法，即图灵试验，⾄今，每年都有试验的⽐赛。

此外，图灵提出的著名的图灵机模型为现代计算机的逻辑⼯作⽅式奠定了基础。

主要成就图灵在科学、特别在数理逻辑和计算机科学⽅⾯，取得了举世瞩⽬的成就，他的⼀些科学成果，构成了现代计算机技术的基础。

计算性理论计算，可以说是⼈类最先遇到的数学课题，并且在漫长的历史年代⾥，成为⼈们社会⽣活中不可或缺的⼯具．那么，什么是计算呢？直观地看，计算⼀般是指运⽤事先规定的规则，将⼀组数值变换为另⼀(所需的)数值的过程．对某⼀类问题，如果能找到⼀组确定的规则，按这组规则，当给出这类问题中的任⼀具体问题后，就可以完全机械地在有限步内求出结果，则说这类问题是可计算的。

这种规则就是算法，这类可计算问题也可称之为存在算法的问题。

这就是直观上的能⾏可计算或算法可计算的概念．在20世纪以前，⼈们普遍认为，所有的问题类都是有算法的，⼈们的计算研究就是找出算法来。