图灵完备

计算机术语

图灵完备是指在可计算性理论里，一系列操作数据的规则（如指令集、编程语言、细胞自动机）按照一定的顺序，可以计算出结果。这个词源于引入图灵机概念的数学家艾伦·图灵。

艾伦·图灵

艾伦·麦席森·图灵，OBE，FRS（英语：Alan Mathison Turing1912年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上设计出世界上第一个电脑程序的国际象棋－洛斯阿拉莫斯国际象棋。

可计算性理论

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

可计算性等级

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

停机问题

停机问题就是判断任意一个程序是否会在有限的时间之内结束运行的问题。该问题等价于如下的判定问题：给定一个程序P和输入w，程序P在输入w下是否能够最终停止。

PCP问题

Post对应问题（Post's correspondence problem）。

不可解度

不可解度的概念定义了不可解的集合之间的相对计算难度。例如，不可解的停机问题显然比任何可解的集合都要难，然而同样不可解的“元停机问题”（即所有具备停机问题的预言机的停机问题）却要难过停机问题，因为具备元停机问题的预言机可以解出停机问题，然而具备停机问题的预言机却不能解出元停机问题。

图灵机

图灵机（英语：Turing machine），又称确定型图灵机，是英国数学家艾伦·图灵于1936年提出的一种抽象计算模型，其更抽象的意义为一种数学逻辑机，可以看作等价于任何有限逻辑数学过程的终极强大逻辑机器。

参见

全国各地天气预报查询

上海市

市辖区