图灵完备

科普中国-科学百科 2018-03-24

　　在可计算性理论里，如果一系列操作数据的规则（如指令集、编程语言、细胞自动机）可以用来模拟单带图灵机，那么它是图灵完备的。这个词源于引入图灵机概念的数学家艾伦·图灵。

　　虽然图灵机会受到储存能力的物理限制，图灵完全性通常指“具有无限存储能力的通用物理机器或编程语言”。

　　艾伦·图灵

　　艾伦·麦席森·图灵，OBE，FRS（英语：Alan Mathison Turing，又译阿兰·图灵，Turing也常翻译成涂林或者杜林，1912年6月23日－1954年6月7日），英国计算机科学家、数学家、逻辑学家、密码分析学家和理论生物学家，他被视为计算机科学与人工智能专家。

　　1931年图灵进入剑桥大学国王学院，毕业后到美国普林斯顿大学攻读博士学位，二战爆发后回到剑桥，后曾协助军方破解德国的著名密码系统Enigma，对盟军取得了二战的胜利有一定的帮助。

　　图灵对于人工智能的发展有诸多贡献，例如图灵曾写过一篇名为《计算机器和智能》（Computing Machinery and Intelligence）的论文，提问“机器会思考吗？”（Can Machines Think?），作为一种用于判定机器是否具有智能的试验方法，即图灵测试。至今，每年都有试验的比赛。此外，图灵提出的著名的图灵机模型为现代计算机的逻辑工作方式奠定了基础。

　　图灵是著名的男同性恋者，并因为其性倾向而遭到当时的英国政府迫害，职业生涯尽毁。他亦患有花粉过敏症。

　　图灵还是一位世界级的长跑运动员。他的马拉松最好成绩是2小时46分3秒，比1948年奥林匹克运动会金牌成绩慢11分钟。1948年的一次跨国赛跑比赛中，他跑赢了同年奥运会银牌得主汤姆·理查兹（Tom Richards）。

　　早期的计算机研究：图灵测试

　　主条目：图灵测试

　　1945年到1948年，图灵在国家物理实验室负责自动计算引擎（ACE）的研究工作。1949年，他成为曼彻斯特大学计算机实验室的副主任，负责最早的真正的计算机---曼彻斯特一号的软件工作。在这段时间，他继续作一些比较抽象的研究，如“计算机械和智能”。图灵在对人工智能的研究中，提出了一个叫做图灵测试（Turing test）的实验，尝试定出一个决定机器是否有感觉的标准。

　　1952年，图灵写了一个国际象棋程序。可是，当时没有一台计算机有足够的运算能力去执行这个程序，他就模仿计算机，每走一步要用半小时。他与一位同事下了一盘，结果程序输了。

　　后来美国新墨西哥州洛斯阿拉莫斯国家实验室的研究组根据图灵的理论，在ENIAC上设计出世界上第一个电脑程序的国际象棋－洛斯阿拉莫斯国际象棋。1

　　可计算性理论

　　在计算机科学中，可计算性理论（Computability theory）作为计算理论的一个分支，研究在不同的计算模型下哪些算法问题能够被解决。相对应的，计算理论的另一块主要内容，计算复杂性理论考虑一个问题怎样才能被有效的解决。

　　可计算性等级

　　这样我们可以定义可计算性等级：所有的语言的集合，记为All；递归可枚举语言，即可以被图灵机枚举的语言的集合，记为RE；递归语言，即可以被图灵机决定的语言的集合，记为R。可见，即形成可计算性等级。那么产生相关的问题即是两个包含关系是不是严格的，即是否有在All而不在RE中的语言，以及在RE而不在R中的语言。阿兰·图灵在1930年代的工作表明这两个包含关系都是不严格的，即可以证明存在语言L_d，是不能被图灵机所枚举的，以及存在语言L_u，是不能被图灵机所决定的。证明的主要思想是对角线法。