为什么是图灵——计算理论的缘起

主要观点总结

本文讨论了丘奇-图灵论题，这是计算机科学的基石，认为图灵机是最广义的计算装置，与所有计算装置等价。文章讨论了丘奇-图灵论题的形成、发展和重要性，提到了计算机科学家、数学家和逻辑学家对论题的不同看法和贡献，以及图灵机和量子计算等概念。同时，也讨论了为什么图灵而不是丘奇或珀斯特被公认为对论题有最大贡献，以及论题在计算机科学中的影响。

关键观点总结

关键观点1: 丘奇-图灵论题定义与重要性

丘奇-图灵论题认为图灵机是最广义的计算装置，是计算机科学的基石，与所有计算装置等价。

关键观点2: 论题的发展与贡献者

哥德尔、丘奇、珀斯特和图灵等人都对论题有贡献，但图灵被认为捕捉到了直觉上的计算概念，并被广泛接受。

关键观点3: 量子计算对论题的挑战

肖尔提出的素数分解的量子算法对强丘奇-图灵论题构成挑战，如果证明不能在多项式时间内求解，将影响论题。

关键观点4: 论题在计算机科学中的影响

论题在计算机科学中起到了连接数学与物理的桥梁作用，影响了计算理论的发展，并可能进一步影响人工智能的哲学问题。

关键观点5: 论题与计算装置

虽然有人期待存在比图灵机更强的生物过程，但图灵机仍然被认为是最强、最广义的机械计算装置。