Church-Turing论题：量子人工智能引论

1936 年，Alonzo.Church 教授和他的博士生Turing 分别利用自己发明的λ 演算和Turing 机模型，探讨了计算的极限是什么。他们得出的结论（或猜想）被称为“Church-Turing”论题，即“所有可以有效计算的函数都可以被通用Turing 机来计算”。

这句话奠定了计算机科学的基础，方向已经指明：造出Turing 机吧，之后就没有我们不能做的了（当然不包括不可判定问题，Turing 他们的本意其实就是向Hilbert 证明存在不可判定问题）。

之所以叫做论题而不是猜想是因为：

（1）“可以有效计算的函数”本身就没有过准确定义，于是不可能被证明。

（2）几乎没有人在乎证明，Turing 机明显已经无比强大了。(https://www.xing528.com)

P 和NP 的定义不应依赖于目前使用的计算模型。在Church-Turing 论题中，任何算法过程都可以在Turing 机上进行模拟。扩展的Church-Turing论题，也被称为Church-Turing 论题，指出在任何物理计算机上，在一定时间内可以计算的所有问题也可以在具有多项式减速的Turing 机上计算。换句话说，任何合理的算法过程都可以在Turing 机上进行模拟，并且有可能出现多项式级的减速，即运行模拟所需的步数。P 问题是在任何物理上合理的计算模型中，多项式时间内解决的问题【60】。

宇宙相当于一个Turing 机的假设，这与Church-Turing 论题有关，类似于数字物理学（Digital Physics）中提出的假设。然而，Richard Feynman 在20世纪80 年代早期观察到，Turing 机器似乎不可能模拟某些量子物理过程而不引起指数级的减速。这一事实与强大的Church-Turing 论题相矛盾，该理论导致Richard Feynman 提出一个问题：量子系统是否可以在假想的量子计算机上模拟。

在1985 年，David Deutsch 根据Richard Feynman 的研究成果重新阐述了Church-Turing 论题：每一个有限可实现的物理系统都可以被运行在有限方式下的通用计算机完美地模拟。由此，Turing 机可被以有限方式运行的通用计算机所取代。