一个学习纯数学的朋友让我考虑下面的问题.
假设有一个名为X的算法有2个输入:A和a_1 ... a_n,其中'A'代表仲裁算法,'a_1..a_n'是A的输入.X接收A及其输入和返回如果带有a_1..a_n的A可以终止,则返回true;如果带有a_1..a_n输入的A落入无限循环(永不结束),则返回false.像这样:
A(n):
while(n<5):
write "I'm immortal!"
结果X(A,6)是真实的,X(A,2)是假的.
那结果是X(X,X)什么？
另外,你知道谁是第一个引入这个问题的人吗？
经过一个小时深入思考后编辑:你能看到一些与Russel悖论相当的东西吗？
Ste*_*sop 19
如果存在,则返回true.证明:假设它返回false.然后它陷入无限循环,永远不会结束.这是一个矛盾.
但更有趣的是程序Y可以从X派生,并且当且仅当其参数不停止时才停止.然后Y(Y,Y)产生矛盾:要么停止(意味着它不停止),要么它不停止(在这种情况下它会停止).因此X不存在.细节被省略了,例如我们已经挥手了一下是否X和Y取一个参数或两个参数.
与这个问题相关的问题在19世纪正在讨论中:David Hilbert的第10个问题(在1900年提出)要求一种算法来确定任何给定的丢番图方程是否有解.事后看来,这可以表示为暂停问题的一个特例:找到一个算法来确定一个强力搜索解决方案是否停止.因此X将解决第10个问题,但X的不存在使第10个问题开放.经过Martin Davis,Julia Robinson,Yuri Matiyasevich等人20年的工作,它终于在1970年关闭.希尔伯特充分说明了"可判定性",在1928年,这是同样的想法停机问题,但是出于测试算术陈述是否真实,而不是测试程序是否停止.
我认为艾伦·图灵发明了必要的术语来陈述停止问题,并证明了结果(1936年).但是Alonzo Church已经证明了lambda演算中存在不可判定的问题(也是1936年),并且Kurt Goedel的不完备性定理(1931)做了很多基础工作,使用他的技术来获得那些可计算性结果可能在两个案例中都比较少问题一直存在(即发明lambda演算和图灵计算模型).
Russell Paradox(1901)的相关性:是的,证明与它们具有相同的形状.在这两种情况下,您都会考虑一个对象,它表示在包含对象本身的类上评估的谓词("所有集合的集合,对程序起作用的程序").你假设它存在,允许你通过修改谓词来构造一个新对象("所有不是自身成员的集合的集合,当且仅当它的输入没有停止时才停止的程序"),当你尝试时产生矛盾评估新的谓词"适用于自己".这反驳了前提("存在一组所有集合","存在一种测试停止的算法").
Topos理论(或其他数学结构分析)中有可能形成相似性,但我不知道那会是什么.
然而,结果之间存在显着的实际差异:X的不存在仅仅证明了停止问题不是由算法决定的,所以如果你是David Hilbert,你必须重新评估你对可能性的期望在数学方面.罗素悖论证明当时使用的集合理论是不一致的,所以如果你是乔治康托尔,你必须重新评估你曾经写过的每一个证据.这引发了第一个正式的公理集合理论,以及Cantor,Dedekind和其他集合理论家的工作的重新陈述,他们一直在研究承认这个悖论的集合的天真定义.