第15课 阿兰图灵

0.可判定性问题

是否存在一种算法，输入正式逻辑语句 输出准确的”是”或”否”答案？

1. 阿隆佐邱奇，Lambda算子

美国数学家 阿隆佐·丘奇，开发了一个叫”Lambda 算子”的数学表达系统，证明其不存在。

2. 图灵机

只要有足够的规则，状态和纸带，图灵机可以解决一切计算问题。和图灵机一样完备，叫做图灵完备。

3. 停机问题

证明图灵机不能解决所有问题。

4. 图灵测试

向人和机器同时发信息，收到的回答无法判断哪个是人，哪个是计算机，则计算机达到了智能程度。