图灵计算密码是穷举吗(图灵密码计算)
图灵计算密码是穷举吗(图灵密码计算)
我个人觉得不是。
所谓的图灵机就是指一个抽象的机器，它有一条无限长的纸带，纸带分成了一个一个的小方格，每个方格有不同的颜色。有一个机器头在纸带上移来移去。机器头有一组内部状态，还有一些固定的程序。
在每个时刻，机器头都要从当前纸带上读入一个方格信息，然后结合自己的内部状态查找程序表，根据程序输出信息到纸带方格上，并转换自己的内部状态，然后进行移动。
现代电子计算机其实就是这样一种通用图灵机的模拟，它能接受一段描述其他图灵机的程序，并运行程序实现该程序所描述的算法。但要注意，它只是模拟，因为现实中的计算机的存储都是有限的，所以无法跨越有限状态机的界限。
经典图灵机及其许多变形识别语言的能力都是相同的，正因为如此，图灵机可以作为计算的一般模型。另外，通用图灵机 (可编程图灵机) 是存在的，通用图灵机可以模拟任意一个图灵机，这也是将图灵机作为现代计算机的形式模型的根本原因
艾伦·麦席森·图灵（英文：Alan Mathison Turing，1912年6月23日-1954年6月7日），英国数学家、逻辑学家，被称为计算机科学父，人工智能之父。1931年图灵进入剑桥大学国王学院，毕业后到美国普林斯顿大学攻读博士学位，第二次世界大战暴发后回到剑桥，后曾协助军方破解德国的著名密码系统Enigma，帮助盟军取得二战的胜利。
1952年，英国振幅对图灵的同性恋取向定罪，随后图灵进行化学阉割（雌激素注射）。1954年6月7日，图灵吃下有氰化物的苹果中毒身亡，享年41岁。2013年12月24日，在英国司法大臣克里斯·格雷灵的要求下，英国女王伊丽莎白二世向图灵颁发了皇家赦免。
图灵对于人工智能的发展有诸多贡献，提出了一种用于判定机器是否具有智能化的试验方法，即图灵试验，至今，每年都有试验的比赛。此外，图灵提出的著名的图灵机模型为现代计算机的逻辑工作方式奠定了基础。
艾伦·麦席森·图灵，1912年6月23日生于英国伦敦。艾伦·麦席森·图灵少年时就表现出独特的直觉创造能力和对数学的爱好。
1926年，14岁的图灵考入伦敦有名的谢伯恩公学去学习，受到良好的中等教育，他在中学期间表现出对自然的极大兴趣和敏锐的数学头脑。
1927年末，年仅15岁的图灵为帮助母亲理解爱因斯坦的相对论，写了爱因斯坦的一部著作的内容提要，表现出他已具备非同凡响的数学水平和科学理解力。
图灵对自然可写的兴趣使他在1930年和1931年两次获得他的一位同学莫克姆的父母设立的自然科学奖，获奖工作中有一篇论文题为“亚硫盐酸和卤化物在酸性溶液中的反应”，受到了政府派来的督学的赞赏，对自然科学的虚拟光驱为他后来的一些研究奠定了基础，他的数学能力使他在念中学时获得过国王爱德华六世数学金盾奖章。
1931年，图灵考进剑桥国王学院，由于成绩优异而获得数学奖学金，在剑桥，他的数学能力得到充分的发展。1935年，他的第一篇数学论文“左右殆周期性的等价”发表于《伦敦数学会杂志》上。同一年，他还写出“论高斯误差函数”一文。这一论文使他又一名大学生直接当选为国王学院的研究员，并与次年荣获英国著名的史密斯（Smith）数学奖，成为国王学院声名显赫的毕业生之一。
1936年5月，图灵向英国权威的数学杂志投了一篇论文，题位《论数学计算在决断难题中的应用》。该文于1937年在《伦敦数学会文集》第42期上发表后立即引起了广泛的注意。在论文的附录里他描述了一可以辅助数学研究的机器，后来我们所熟知的电脑，以及还没有实现的”人工智能“都基于这个设想。这是他人生第一篇重要文章，也是他的成名之作。
1937年，图灵发表的另一篇文章“可计算性与λ可定义性”则拓广了丘奇（Church）提出的“丘奇论点”，形成“丘奇-图灵论点”，对计算机理论的严格化，对计算机科学的形成和发展都具有奠基性的意义。
1936年9月，图灵应邀到美国普林斯顿高级研究院学习，并于丘奇一同工作。
在美国期间，他对群论做了一些研究，并撰写了博士论文。1938年在普林斯顿获得博士学位，其论文题目为“以序数为基础的逻辑系统”，1939年正式发表，在数理逻辑研究中产生了深远的影响。
1938年夏，图灵回到英国，仍在剑桥大学国王学院任研究员，继续研究数理逻辑和计算理论，同时开始了计算机的研制工作。
第二次世界大战打断了图灵的正常研究工作，1939年秋，他应召到英国外交部通信处从事军事工作，主要是破译敌方密码的工作。由于破译工作的需要，他参与了世界上最早的电子计算机的研制工作。他的工作取得了极好的成就，因而于1945年获政府的最高奖——大英帝国荣誉勋章（O.B.E.勋章）。
1945年，图灵结束了在外交部的工作，他试图恢复战前在理论计算机科学方面的研究，并结合战时的工作，具体研制出新的计算机来。这一想法得到当局的支持。同年，图灵被录用为泰丁顿Teddington）国家物理研究所的研究人员，开始从事“自动计算机” （ACE） 的逻辑设计和具体研制工作。这一年，图灵写出一份长达50页的关于ACE的设计说明书。这一说明书在保密了27年之后，于1972年正式发表。在图灵的设计思想指导下，1950年制出了ACE样机，1958年制成大型ACE机。人们认为，通用计算机的概念就是图灵提出来的。
1945年到1948年，他在英国国家物理实验室工作，负责自动计算引擎的研究。
1946年的8月，图灵参加了他正式跑步训练后的第一个比赛。那是在他加入沃尔顿田径俱乐部后参加的3英里 （4.8公里） 比赛，图灵以15分37秒的成绩夺得第一，这一成绩当年在英国排名第20位。
1947年，在莱斯特郡拉夫堡 （Loughborough） 大学体育场举行的英国业余田径协会马拉松锦标赛上，图灵跑出了他在马拉松赛中的个人最好成绩2小时46分03秒，在那场比赛中列第五名。
1948年，图灵接受了[曼彻斯特大学]的高级讲师职务，并被指定为曼彻斯特自动数字计算机(Madam)项目的负责人助理，具体领导该项目数学方面的工作，作为这一工作的总结。
1949年成为曼彻斯特大学计算机实验室的副主任，负责最早的真正意义上的计算机——“曼彻斯特一号”的软件理论开发，因此成为世界上第一位把计算机实际用于数学研究的科学家。
1950年，图灵编写并出版了《曼彻斯特电子计算机程序员手册》（The programmers’handbook for the Manchester electronic computer）。这期间，他继续进行数理逻辑方面的理论研究。并提出了著名的“图灵测试”。同年，他提出关于机器思维的问题，他的论文“计算机和智能（Computingmachiery and intelligence），引起了广泛的注意和深远的影响。1950年10月，图灵发表论文《机器能思考吗》。这一划时代的作品，使图灵赢得了“人工智能之父”的桂冠。
1951年，由于在可计算数方面所取得的成就，成为英国皇家学会会员，时年39岁。
1952年，他辞去剑桥大学国王学院研究员的职务，专心在曼彻斯特大学工作．除了日常工作和研究工作之外，他还指导一些博士研究生，还担任了制造曼彻斯特自动数字计算机的一家公司——弗兰蒂公司的顾问。
1952年，图灵写了一个国际象棋程序。可是，当时没有一台计算机有足够的运算能力去执行这个程序，他就模仿计算机，每走一步要用半小时。他与一位同事下了一盘，结果程序输了。后来美国新墨西哥州洛斯阿拉莫斯国家实验室的研究群根据图灵的理论，在MANIAC上设计出世界上第一个电脑程序的象棋。
1952年，图灵的同性伴侣协同一名同谋一起闯进了图灵的房子实施盗窃。图灵为此而报警。但是警方的调查结果使得他被控以“明显的猥亵和性颠倒行为”（同性恋）。他没有申辩，并被定罪。在著名的公审后，他被给予了两个选择：坐牢或 荷尔蒙疗法 。他选择了荷尔蒙注射，并持续了一年。在这段时间里，药物产生了包括乳房不断发育的副作用。
1954年6月7日，图灵被发现死于家中的床上，床头还放着一个被咬了一口的泡过氰化物的苹果。警方调查后认为是剧毒的氰化物中毒，调查结论为自杀。当时图灵41岁。
2009年，英国计算机科学家康明（John Graham-Cumming）发起了为图灵平反的在线请愿，截止到2009年9月10日请愿签名人数已经超过了3万，为此，当时的英国政府及首相戈登布朗不得不发表正式的道歉声明。
2012年12月，霍金、纳斯（Paul Nurse，诺贝尔医学奖得主）、里斯（Martin Rees，[英国皇家学会会长）等11位重要人士致函英国首相卡梅伦，要求为其平反。
2013年12月24日，在英国司法大臣克里斯・格雷灵（ChrisGrayling）的要求下，英国女王终于向图灵颁发了皇家赦免。英国司法部长宣布，“图灵的晚年生活因为其同性取向而被迫蒙上了一层阴影，我们认为当时的判决是不公的，这种歧视现象如今也已经遭到了废除。为此，女王决定为这位伟人送上赦免，以此向其致敬。”
图灵在他的“论可计算数及其在判定问题中的应用”一文中从一个全新的角度定义了可计算函数。他全面分析了人的计算过程，把计算归结为最简单、最基本、最确定的操作动作，从而用一种简单的方法来描述那种直观上具有机械性的基本计算程序，使任何机械(能行)的程序都可以归约为这些动作。这种简单的方法是以一个抽象自动机概念为基础的，其结果是：算法可计算函数就是这种自动机能计算的函数。这不仅给计算下了一个完全确定的定义，而且第一次把计算和自动机联系起来，对后世产生了巨大的影响，这种“自动机”后来被人们称为“图灵机”。
图灵在第二次世界大战中从事的密码破译工作涉及到电子计算机的设计和研制，但此项工作严格保密。直到70年代，内情才有所披露。从一些文件来看，很可能世界上第一台电子计算机不是ENIAC，而是与图灵有关的另一台机器，即图灵在战时服务的机构于1943年研制成功的CO-LOSSUS(巨人)机，这台机器的设计采用了图灵提出的某些概念。它用了1500个电子管，采用了光电管阅读器；利用穿孔纸带输入；并采用了电子管双稳态线路，执行计数、二进制算术及布尔代数逻辑运算，巨人机共生产了10台，用它们出色地完成了密码破译工作。战后，图灵任职于泰丁顿国家物理研究所(Teddington National Physical Laboratory)，开始从事“自动计算机”(Automatic Computing Engine)的逻辑设计和具体研制工作。1946年，图灵发表论文阐述存储程序计算机的设计。他的成就与研究离散变量自动电子计算机（Electronic Discrete Variable Automatic Computer）的约翰·冯·诺伊曼（John von Neumann）同期。图灵的自动计算机与诺伊曼的离散变量自动电子计算机都采用了二进制，都以“内存储存程序以运行计算机”打破了那个时代的旧有概念。
从1952年直到去世，图灵一直在数理生物学方面做研究。他在1952年发表了一篇论文《形态发生的化学基础》(The Chemical Basis of Morphogenesis)。他主要的兴趣是斐波那契叶序列，存在于植物结构的斐波那契数。他应用了反应-扩散公式，如今已经成为图案形成范畴的核心。他后期的论文都没有发表，一直等到1992年《艾伦·图灵选集》出版，这些文章才见天日。
1945年到1948年，图灵在国家物理实验室，负责自动计算引擎（ACE）的工作 。1949年，他成为曼彻斯特大学计算机实验室的副主任，负责最早的真正的计算机---曼彻斯特一号的软件工作。在这段时间，他继续作一些比较抽象的研究，如“计算机械和智能”。图灵在对人工智能的研究中，提出了一个叫做图灵试验的实验，尝试定出一个决定机器是否有感觉的标准。
CCCF第7期专题邀请了相关领域的6位专家学者深入探讨图灵对密码学发展的深远影响和密码学的前沿进展，涵盖了密码设计与密码分析这两个密码学的组成部分，同时兼顾了广度与深度。各专题文章原文详见CCF数字图书馆。
关键词： 密码学 图灵 网络空间安全 信息安全
从早期作为一种实用性技术，到今天发展为一门严谨的学科，密码学的发展史汇聚了人类文明的聪明才智。围绕着如何使用密码实现安全和隐私保护与如何安全地使用密码这两个本质问题，密码的设计与分析相互依存，相互促进，处在不断的博弈中，这使得密码的研究得到了持续的发展。
在发展过程中，计算机科学之父艾伦·图灵(Alan M. Turing)做出了多方面本质的贡献，对密码学的成熟产生了深远的影响。首先，在密码安全定义建模方面，图灵的可计算性理论及其发明的（通用）图灵机起着重要的作用。例如，我们知道在现代密码中，设计者首先需要证明其提出的密码算法或者协议可以抵御所有的已知和未知的攻击。然而，有很多密码算法或者协议无法证明自己是安全的，但也无法找到安全漏洞。在这种情况下，是设计者没有找到正确的证明方法呢？还是这个密码算法或者协议本身就不可能被证明呢？图灵奠基的可证明性理论对这些问题给出了答案，那就是很多我们无法证实或者证伪的密码算法或者协议，并不是由于设计者缺少正确的证明方法，而是这个密码算法或者协议本身就不可能在有限步骤内被证明。这就要求设计者不断地对其密码算法或者协议进行修改，使得其能被证明。此外，图灵发明的（通用）图灵机也被广泛应用于密码算法或协议敌手模型中对敌手的建模，使对敌手的运算时间约束可以转化成对于算法的计算步骤限制。目前被密码学界广泛接纳的通用可组合安全模型(universal composability)就是通过多项式时间通用图灵机来模拟敌手的。
本期专题邀请了相关领域的专家学者深入探讨图灵对密码学发展的深远影响和密码学的前沿进展，共组织了六篇文章，涵盖了密码设计与密码分析这两个密码学的组成部分，同时兼顾了广度与深度。
第一篇文章是由英国兰卡斯特大学助理教授张秉晟和浙江大学研究员秦湛联合撰写的《通用图灵机及其对现代密码安全建模的影响》，以（通用）图灵机的计算理论为切入点，深入浅出地分析（通用）图灵机对密码学基本算法工具的安全定义和对密码协议的安全性建模产生的深远影响。作者介绍了密码学中的加密算法是如何从AES时代逐渐演化到现在的可证明安全定义以及（通用）图灵机在其中起到的作用。另外，作者还梳理了密码协议，例如安全多方计算的安全性建模和定义是如何通过几十年的研究探讨演化到如今的通用可组合安全模型，重点解析了交互式图灵机对整个通用可组合安全模型构架的奠基作用。
第二篇文章是由山东大学教授王美琴等撰写的《从图灵破解Enigma到现代密码分析》，介绍了Enigma密码机的工作原理和图灵对Engima密码机的破解，并且解析了Enigma密码机的破解对现代密码分析的影响。作者还以针对哈希函数的破解实例来呈现现代密码分析对安全密码算法设计的重要性。
第三篇文章是由中国科学院信息工程研究所研究员胡磊和副研究员宋凌撰写的《密码杂凑函数的回顾与进展》，介绍了用于实现密码学研究中的完整性和认证性的一类关键密码学函数——密码杂凑函数（又称哈希函数、散列函数等）。作者阐述了密码杂凑函数的性质及其具体应用，梳理了密码杂凑函数的发展脉络，总结了密码分析对密码杂凑函数标准化的影响，并具体介绍美国国家标准与技术研究院(NIST)杂凑函数标准SHA-3及其最新分析进展。
第四篇文章是由香港城市大学副教授王聪和武汉大学教授王骞等联合撰写的《安全多方计算理论与实践》，从理论和实践的双重角度对安全多方计算进行深入的解析。作者从生动的现实问题入手，介绍了安全多方计算的系统模型、安全模型以及理论上的普适性解决方案。同时，文章还梳理了安全多方计算在实际应用中的前沿进展，总结了当前安全多方计算应用的现状，指出了未来安全多方计算的研究方向。
第五篇文章是由美国新泽西理工学院助理教授唐强和哥伦比亚大学教授慕梯·杨(Moti Yung)联合撰写的《抗后门的新一代密码学Cliptography研究进展》，对密码学的通用后门攻击Kleptography进行了系统的总结，并且介绍了抗后门密码学Cliptography的前沿进展。作者先阐述了密码学后门背后的科学原理，回答了如何在设计之初就考虑到这种可能的后门攻击问题，进而介绍了抗后门密码学Cliptography如何弥合这个密码学理论设计与实际实现之间的鸿沟，并对新一代密码学理论基础和密码标准提出新的建议。
第六篇文章是由浙江大学副教授张帆、上海交通大学教授谷大武等撰写的《人工智能之于旁路分析》，介绍了人工智能技术在密码旁路分析领域的研究现状，梳理了机器学习算法在旁路分析领域的发展过程，剖析了人工智能技术在密码旁路分析领域取得成果的原因，并指出了将人工智能技术与旁路分析领域结合的研究方向。
希望本专题能鼓舞更多的学者和安全从业人员参与到网络空间安全和信息安全的研究中，设计与分析新密码算法和协议，开拓新的研究方向和领域。
作者介绍
任 奎
CCF专业会员。浙江大学网络空间安全研究中心主任，国家千人计划特聘教授。主要研究方向为数据安全，云安全，人工智能安全，物联网安全等。kuiren@zju.edu.cn
CCF推荐
【精品文章】
点击 “阅读原文” ，前往CCF数图相关栏目。
知识点：图灵测试，是现代计算机之父阿兰-图灵在1950年提出的，想考量的问题是：机器能否思考。
图灵测试，如果你感觉这个词比较陌生，我们就先来解释一下：图灵测试是测试人(多人)在与被测试者(一个人和一台机器)隔开的情况下，通过一些装置(如键盘)向被测试者随意提问。问过一些问题后，如果测试人中超过30%的人不能根据答复确认被测试者哪个是人，哪个是机器，那么这台机器就通过了测试，并被认为具有人类智能。
这个看似无厘头的测试，是由现代计算机科学之父英国人阿兰?图灵在60多年前提出的。1950年，阿兰·图灵在那篇名垂青史的论文《计算机械与智力》的开篇说：“我建议大家考虑这个问题：‘机器能思考吗？’”
但是由于我们很难精确地定义思考，所以图灵提出了他所谓的“模仿游戏”：
一场正常的模仿游戏有ABC三人参与，A是男性，B是女性，两人坐在房间里；C是房间外的裁判，他的任务是要判断出这两人谁是男性谁是女性。男方是带着任务来的：他要欺骗裁判，让裁判做出错误的判断。
那么，图灵问：“如果一台机器取代了这个游戏里的男方的地位，会发生什么？这台机器骗过审问者的概率会比人类男女参加时更高吗？这个问题取代了我们原本的问题：‘机器能否思考？’”
这，就是图灵测试的本体。
在科幻片《银翼杀手》中，我们看到了图灵测试的一个具体应用。在电影里用一种情感测试来区分人类与人造人。
虽然2014年6月7日发生了一件事情：聊天程序“尤金·古斯特曼”(Eugene Goostman)在英国皇家学会举行的2014图灵测试大会上冒充一个13岁乌克兰男孩而骗过了33%的评委，从而按照图灵当初的定义，“通过”了图灵测试。但实际上，在现实生活中，图灵测试的原始形式很少被使用。不过，我们实际大量使用图灵测试的另外一种简化的形式——校验码。校验码的用处是区分操作者是人还是机器人。仅仅通过一个简单的测试问题：能否从一个图片中看出里面写的是什么文字。
推广图灵测试的内在含义，实际是一种真假鉴别。如果这样来说，社会上的资格考试本身也是一种图灵测试。出题人面对大量考生，他们必须区分出来哪些是具有资格的人，哪些是不具有资格的人。为了方便操作，一般很少依赖阅卷人的主观判断，而是通过仔细设计题目来实现这一点。
最后再看一个很好玩的图灵测试的反向运用：怎么证明自己不是神经病。目前来看，最好的办法就是不去试图证明什么。凡是试图证明什么的人，看起来多多少少都有点像神经病。不过，葛优在电影《大腕》里，给了我们另外一个思路，他讲了一个笑话，最后一句“三楼的楼长就是你了”，让医生明白了这个家伙思维正常。能够给别人设置思维圈套，然后自己跳出来，看来这个也是具备正常思维能力的一种表现。
图片来源于网络
本作品为“科普中国-科学原理一点通”原创 转载时务请注明出处
更多精彩内容，敬请关注科学原理一点通官方网站
微信公众平台（ID：kxylydt）
图灵测试是测试人在与被测试者(一个人和一台机器)隔开的情况下，通过一些装置（如键盘）向被测试者随意提问。问过一些问题后，如果被测试者超过30%的答复不能使测试人确认出哪个是人、哪个是机器的回答，那么这台机器就通过了测试，并被认为具有人类智能。图灵测试 2014 的举办方英国雷丁大学发布新闻稿，宣称俄罗斯人弗拉基米尔·维西罗夫（Vladimir Veselov）创立的人工智能软件尤金·古斯特曼（Eugene Goostman）通过了图灵测试。如果这一结论获得确认，那么这将是人工智能乃至于计算机史上的一个里程碑事件。
阿兰·图灵英国数学家、逻辑学家，被视为计算机科学之父。 1931年图灵进入剑桥大学国王学院，毕业后到美国普林斯顿大学攻读博士学位，二战爆发后回到剑桥，后曾协助军方破解德国的著名密码系统Enigma，帮助盟军取得了二战的胜利。
1936年，图灵向伦敦权威的数学杂志投了一篇论文，题为“论数字计算在决断难题中的应用”。在这篇开创性的论文中，图灵给“可计算性”下了一个严格的数学定义，并提出著名的“图灵机”(Turing Machine)的设想。“图灵机”不是一种具体的机器，而是一种思想模型，可制造一种十分简单但运算能力极强的计算装置，用来计算所有能想象得到的可计算函数。“图灵机”与“冯·诺伊曼机”齐名，被永远载入计算机的发展史中。
1950年10月，图灵又发表了另一篇题为“机器能思考吗”的论文，成为划时代之作。也正是这篇文章，为图灵赢得了“人工智能之父”的桂冠。
阿兰图灵是数学题是计算机学之父创作的，1936年，图灵向伦敦权威的数学杂志投了一篇论文，题为“论数字计算在决断难题中的应用”的数学题。
阿兰.图灵出生于1912年的英国伦敦，他自小就展现出了极高的智商，三岁可以自行读书，五岁便写下了关于显微镜的观察作文。
但图灵的性格是极其孤僻的，不善于表达，因此图灵在少年期间，就成为了被霸凌的对象。就在这种环境之下，一个改变图灵一生的学长出现了，这个学长保护了图灵，制止了其他人对图灵的霸凌行为，同时这个学长和图灵有着相同的爱好，他们对数学和科学都有着极大的兴趣，经常在一起讨论这方面的知识。
后来，他在1931年考入了剑桥大学国王学院，毕业后到美国普林斯顿大学攻读博士学位，第二次世界大战爆发后回到剑桥，后来发生的事情大家也都知道了，图灵帮助英国破解了德国的“恩格玛”密码机器，帮助英国取得了二战的胜利，成为了世界的英雄、
图灵作为著名数学家，所贡献的成就完全不止于密码破译这一个领域，图灵对人类的计算机技术发展，和人工智能的技术发展，都做出了很大的贡献。
例如图灵曾写过一篇名为《计算机器和智能》的论文，在计算机科学界引起了巨大震撼同时图灵花费4万英镑，成功研制出了一台计算机，这台计算机是当时世界上速度最快，功能最强的计算机，为后来的计算机发展奠定了坚实的基础。
后来图灵又提出了“机器会思考吗”这一问题，并设计了著名的“模仿游戏试验”，后人称之为“图灵测试”。
阿兰图灵数学题现状
牛津大学的数学家Marc Lackenby找到了一种算法，能比以往任何算法都更快判断一个纽结是否为“平凡纽结”。这种算法可以在所谓的“准多项式时间（quasi-polynomial time）”，判断出一个交叉数为n的纽结图所代表的的纽结是否是平凡纽结。
以上内容参考：艾伦·麦席森·图灵 - 百度百科
