图灵在计算机理论方面的贡献

1. 提出计算机的概念

1945 年， 图灵恢复在理论计算机科学方面的研究， 并结合战时的工作， 具体研制出新的计算机来。 同年， 图灵开始从事“自动计算机” (ACE)的逻辑设计和具体研制工作。1950 年制出了 ACE 样机， 1958 年制成大型 ACE 机。

2. 把可计算函数定义为图灵机可计算函数．

1937 年， 图灵在他的“可计算性与λ 可定义性” 一文中证明了图灵机可计算函数与λ 可定义函数是等价的， 得出： 算法(能行)可计算函数等同于一般递归函数或λ 可定义函数或图灵机可计算函数． 这就是“丘奇‐图灵论点”， 相当完善地解决了可计算函数的精确定义问题， 对数理逻辑的发展起了巨大的推动作用。

3. 开创了“自动机” 这一学科分支， 促进了电子计算机的研制工作．

4. 提出了通用图灵机的概念

它相当于通用计算机的解释程序， 这一点直接促进了后来通用计算机的设计和研制工作，在给出通用图灵机的同时， 图灵就指出， 通用图灵机在计算时， 其“机械性的复杂性”是有临界限度的， 超过这一限度， 就要靠增加程序的长度和存贮量来解决． 这种思想开启了后来计算机科学中计算复杂性理论的先河。

5. 解决了著名的希尔伯特判定问题

狭谓词演算公式的可满足性的判定问题。 他用一阶逻辑中的公式对图灵机进行编码， 再由图灵机停机问题的不可判定性推出一阶逻辑的不可判定性。 他在此处创用的“编码法”成为后来人们证明一阶逻辑的公式类的不可判定性的主要方法之一。

6. 图灵测试

1946 年， 图灵发表论文阐述存储程序计算机的设计。 图灵的自动计算机与诺伊曼的离散变量自动电子计算机都采用了二进制， 都以“内存储存程序以运行计算机” 打破了那个时代的旧有概念。

7. 人工智能人工智能

致力研发运行 Manchester Mark 1 型号储存程序式计算机所需的软件。 1950 年他发表论文《计算机器与智能》， 为后来的人工智能科学提供了开创性的构思。 提出著名的“图灵测试”， 指出如果第三者无法辨别人类与人工智能机器反应的差别， 则可以论断该机器具备人工智能。