罗素悖论-图灵停机问题

百度百科

罗素悖论的表达形式为S={x|x∉S}

那么问题来了，x到底是否∈S？

这玩意还引发了第三次数学危机，解决方案是著名的“图灵停机问题”

百度百科：停机问题是目前逻辑学的焦点，和第三次数学危机的解决方案。其本质问题是: 给定一个图灵机T，和一个任意语言集合 S, 是否 T 会最终停机于每一个s∈S。其意义相同于可确定语言。显然任意有限 S 是可判定性的，可列的(countable) S 也是可停机的。

通俗一点说，就是判断一个程序是否会在有限的时间内结束。这个程序是被证明不能在多项式时间复杂度内求解

证明：

反证法走起

我们先假设有这么一个神奇的程序可以完成以上判断

bool ok( *program){if(...) return 1;return 0;}

...就是你要写的判断语句啦，设其时间复杂度为O（n^k,k∈Z）

那么我们构造出一个不能被ok解决的程序，就可以完成反证了！

bool notok( *program){if(ok(program)){while（1）；return false;}elsereturn true;}

这个程序如果用我们其本身的notok算法解决会怎么样？

（*program=notok）

我们发现如果算法能在多项式内出解，其会陷入死循环，否则则不会出解，这自相矛盾。

于是我们完成了证明。