汉语是联合国官方正式使用的 6 种同等有效语言之一。请不要歧视汉语！

Chinese is one of the six equally effective official languages of the United Nations.

Not to discriminate against Chinese, please!

[小资料] 丘奇-图灵论题（The Church-Turing thesis）

丘奇-图灵论题： The Church-Turing thesis

算法： algorithm

计算模型： models of computation

   算法的严格定义由丘奇-图灵论题（Church-Turing Thesis）来界定，该论题说，一个问题有算法，当且仅当该问题可用处处停机的图灵机来计算，处处停机是指在所有输入上都在有限步之内停机，图灵机计算一个问题是指在所有输入上都给出正确答案。

2022-06-16，算法/algorithm/许可，中国大百科全书，第三版网络版[DB/OL]

https://www.zgbk.com/ecph/words?SiteID=1&ID=107183&Type=bkzyb&SubID=81665

图1  Left: Alonzo Church. Right: Alan Turing (Photos: Princeton University)

左图：阿隆佐·丘奇。右图：艾伦·图灵（照片：普林斯顿大学）

https://911weknow.com/wp-content/uploads/2020/09/uncomputable-numbers-2.png

https://911weknow.com/uncomputable-numbers

打听： 

   （1）“根号2”（实数）是一种合理的存在吗？“根号2”能被图灵机正确处理吗？

   （2）“几何曲线”（实数的幂集）是一种合理的存在吗？“几何曲线”能被图灵机正确处理吗？

   （3）人类“手舞足蹈”（几何曲线的幂集）是一种合理的存在吗？“手舞足蹈”能被图灵机正确处理吗？

   上面的合理的存在，是指满足下列之一或更多：

   合乎逻辑的，具有某种数学上的合理性，或是现实世界中“客观”存在。

图2  舞蹈里的重复练习，做起来很苦，坚持下来很酷

https://p7.itc.cn/images01/20220404/6e92ab5c17144577996212882e3fa67b.jpeg

https://learning.sohu.com/a/535225639_121275483

参考资料：

[1] 2023-02-06，玻色采样计算模型/Bose sampling computational model/陈平形，中国大百科全书，第三版网络版[DB/OL]

https://www.zgbk.com/ecph/words?SiteID=1&ID=506420&Type=bkzyb&SubID=222532

   因此玻色采样模型是一个可物理实现的专用量子计算模型，有望检验扩展的邱奇-图灵论题（Church-Turing thesis），在量子计算和计算复杂性理论方面都有重要意义。

[2] 2022-11-23，计算模型/models of computation/眭跃飞，中国大百科全书，第三版网络版[DB/OL]

https://www.zgbk.com/ecph/words?SiteID=1&ID=305744&Type=bkzyb&SubID=81691

   由于算法是一个直观的和非形式的定义的概念，而图灵机是严格的形式定义的概念。要证明所有图灵机可计算的自然数上函数等于所有算法可计算的函数，这是一件不可能证明的事情。

[3] 2022-06-16，算法/algorithm/许可，中国大百科全书，第三版网络版[DB/OL]

https://www.zgbk.com/ecph/words?SiteID=1&ID=107183&Type=bkzyb&SubID=81665

   算法的每条规则或指令必须是能行的（effective），即可用有限的硬件在有限的时间和空间内实现。

[4] 2023-09-23，计算机科学中的逻辑/logics in computer science/眭跃飞，中国大百科全书，第三版网络版[DB/OL]

https://www.zgbk.com/ecph/words?SiteID=1&ID=218532&Type=bkzyb&SubID=81639

   美国数学家A.丘奇（Alonzo Church，1903～1995）提出了丘奇-图灵假设（Church-Turing thesis）：所有算法可计算的函数是图灵可计算的。

[5] Church thesis. Encyclopedia of Mathematics.

https://encyclopediaofmath.org/wiki/Church_thesis

   The thesis of Church cannot be strictly proved, since its formulation involves the inexact notion of "algorithm in the intuitive sense" . There were attempts to refute Church' thesis, but they have not led to success (1984).

   Church的论点不能被严格证明，因为它的公式涉及“直觉意义上的算法”这一不精确的概念。有人试图反驳Church的论点，但都没有成功（1984）。

[6] Stanford Encyclopedia of Philosophy, 2023-12-18, The Church-Turing Thesis

https://plato.stanford.edu/entries/church-turing/

[7] Apostolos Syropoulos, 2008, Hypercomputation, Computing Beyond the Church-Turing Barrier

https://link.springer.com/book/10.1007/978-0-387-49970-3

[8] 2023-10-17，模拟计算机/analog computer/陈文光，中国大百科全书，第三版网络版[DB/OL]

https://www.zgbk.com/ecph/words?SiteID=1&ID=207401&Type=bkzyb&SubID=81428

   模拟计算机是计算机的一种实现形式，利用机械、液压、电子等连续变化的物理量来表示数据，通过模拟的方式完成计算，解决问题。

[9] 2023-08-24，数学仿真/mathematical simulation/李琦，中国大百科全书，第三版网络版[DB/OL]

https://www.zgbk.com/ecph/words?SiteID=1&ID=58602&Type=bkzyb&SubID=63122

   60～70年代，由于数字计算机技术还处于较低水平时，产生了数字-模拟混合仿真，即将系统的模型分为两部分，其中一部分放在模拟计算机上运行，另一部分放在数字计算机上运行，两个计算机之间利用模数和数模转换装置交换信息，这就是数字-模拟混合仿真。

[10] Alonzo Church, MacTutor History of Mathematics Archive

https://mathshistory.st-andrews.ac.uk/Biographies/Church/

[11] Alonzo Church, National Academy of Sciences

https://nasonline.org/member-directory/deceased-members/56941.html

[12] Alonzo Church, Stanford Encyclopedia of Philosophy

https://plato.stanford.edu/entries/church/index.html

相关链接：

[1] 2024-01-24，[道德经，自然运算，恸哭] “道可道非常道”与“自然运算”的计算机整机理论模型

https://blog.sciencenet.cn/blog-107667-1419227.html

[2] 2024-01-07，[搜集，小资料] 理论计算机模型的名字

https://blog.sciencenet.cn/blog-107667-1417022.html

[3] 2024-01-05，[笔记，请教，原创] “自然运算”信息设备的一般理论模式

https://blog.sciencenet.cn/blog-107667-1416810.html

[4] 2024-01-04，[请教，讨论] 什么是超过“图灵机”能力的更强的计算机？

https://blog.sciencenet.cn/blog-107667-1416691.html

[5] 2024-03-30，[笔记，数学文化] 用清晰的思想代替盲目的计算：香农的信息熵（Claude Elwood Shannon）

https://blog.sciencenet.cn/blog-107667-1427605.html

感谢您的指教！

感谢您指正以上任何错误！

感谢您提供更多的相关资料！