哥德尔不完备定理与停机问题

喜欢ヅ旅行 2024-04-20 11:45 15阅读 0赞

## 哥德尔不完备定理 ##

哥德尔不完备定理是库尔特·哥德尔(Kurt Friedrich Gödel)于1931年证明并发表的两条定理。简单地说，第一条定理指出：

> 任何自洽的形式系统，只要蕴涵皮亚诺算术公理，就可以在其中构造在体系中不能被证明的真命题，因此通过推理演绎不能得到所有真命题

把第一条定理的证明过程在体系内部形式化后，哥德尔证明了第二条定理。该定理指出：

> 任何逻辑自洽的形式系统，只要蕴涵皮亚诺算术公理，它就不能用于证明其本身的自洽性。

我们在这里不证明哥德尔不完备定理，仅仅用它说明停机问题。

## 停机问题 ##

停机问题就是判断任意一个[程序][Link 1]是否能在有限的时间之内结束运行的问题。该问题等价于如下的判定问题：

是否存在一个程序P，对于任意输入的程序w，能够判断w会在有限时间内结束或者[死循环][Link 2]。

## 停机问题可解吗 ##

> 任何自洽的形式系统，只要蕴涵皮亚诺算术公理，就可以在其中构造在体系中不能被证明的真命题，因此通过推理演绎不能得到所有真命题

从这条定理我们可以得知，首先在程序中一定会出现编译器无法检查出，却实际上会造成错误的语句。比如一台打印机，输入P\*X这条指令会打印X，输入NP\*X则一定不会打印X，那么如果我输入P\*NP\*NP\*会怎么样呢？

> 任何逻辑自洽的形式系统，只要蕴涵皮亚诺算术公理，它就不能用于证明其本身的自洽性。

这条定理又意味着一个系统无法判断自己到底一不一致，也就是说如果假定系统是相容的，最后证明的结果就是不相容的，这个用数学解释起来比较难懂，我们可以用著名的罗素悖论来理解

> 一座小城里有位理发师, 他有一项规定: **他给并且只给那些不给自己理发的人理发.**他该给自己理发吗？

在编程中，我们可以理解为有一个程序p，它的功能是接受一个函数，并判断这个函数是否能够结束（停机），如果结束了返回true，如果无法结束就返回false，这恰好就是停机问题！

由哥德尔不完备定理我们可以得知永远不会有这么一个程序出现。

## 总结 ##

哥德尔不完备定理告诉了我们没有完美的数学系统，所以更没有完美的程序。

我们不能过于依赖编译器的错误提示，来不管不顾的使用丑陋的代码完成业务功能，只要能跑起来就行。

功能的错误是很好解决的，但是不清晰的代码造成的混乱才是问题的根源。

要记住，代码能跑起来并不意味着写出了正确的程序，只不过是这个世界的缺陷才让垃圾代码通过了编译，使用高密度的逻辑几行解决问题的代码通常要比废话连篇的代码造成的混乱更多！

[Link 1]: https://zh.wikipedia.org/wiki/%E7%A8%8B%E5%BA%8F
[Link 2]: https://zh.wikipedia.org/wiki/%E6%AD%BB%E5%BE%AA%E7%92%B0

发表评论取消回复

表情：

评论列表（有 0 条评论，15人围观）

还没有评论，来说两句吧...

相关阅读

相关哥德尔不完备定理与停机问题

哥德尔不完备定理哥德尔不完备定理是库尔特·哥德尔(Kurt Friedrich Gödel)于1931年证明并发表的两条定理。简单地说，第一条定理指出： > 任何...

喜欢ヅ旅行/ 2024年04月20日 11:45/ 0 赞/ 16 阅读

相关德尔福15326654_德尔福ORM

德尔福15326654 Working with database data in Delphi can be really simple. Drop a TQuery on

电玩女神/ 2022年12月07日 12:13/ 0 赞/ 227 阅读

相关哥德巴赫猜想

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhp

快来打我*/ 2022年11月12日 02:38/ 0 赞/ 172 阅读

相关哥德尔90年前的「不完备性定理」，奠定了计算机与AI的理论基础

机器之心报道编辑：蛋酱、小舟 > 大神早已远去，而他的光芒仍在人间。 ![哥德尔90年前的「不完备性定理」，奠定了计算机与AI的理论基础][90_AI] 193

约定不等于承诺〃/ 2022年10月07日 14:55/ 0 赞/ 2 阅读

相关哥德巴赫猜想

哥德巴赫猜想：任一大于2的偶数，都可表示成两个素数之和。 \---------------------------------验证----------------------

逃离我推掉我的手/ 2022年09月10日 03:28/ 0 赞/ 195 阅读

相关哥德巴赫猜想

哥德巴赫猜想 Time Limit: 4000ms Memory limit: 10000K 有疑问？点这里^\_^ 题目描述哥德巴赫猜想：对于任一个大于或

比眉伴天荒/ 2022年08月10日 05:51/ 0 赞/ 208 阅读

相关哥德巴赫猜想

<span style="font-size:14px;">世界三大数学猜想编辑即<span style="color:FF0000;">费马猜想、四色猜想和

喜欢ヅ旅行/ 2022年08月07日 11:41/ 0 赞/ 251 阅读

相关哥德巴赫猜想

<table> <tbody> <tr> <td colspan="3"> <p>哥德巴赫（<span style="font-family:Times Ne

悠悠/ 2022年06月16日 22:10/ 0 赞/ 240 阅读

相关哥德巴赫猜想

[哥德巴赫猜想][Link 1]（ Goldbach Conjecture）大致可以分为两个猜想（前者称“强”或“二重哥德巴赫猜想”后者称“弱”或“三重 [哥德巴赫][Link

小灰灰/ 2022年01月06日 21:27/ 0 赞/ 250 阅读

相关德尔福基础

并行 http://docwiki.embarcadero.com/RADStudio/Tokyo/en/Using\_TParallel.For\_from\_the\_P

曾经终败给现在/ 2021年12月15日 12:49/ 0 赞/ 264 阅读