数学联邦政治世界观
超小超大

图灵机和数学公理体系是什么关系?

字面上说这两个关系不是很大:哥德尔不完备定理中的完备是指形式系统S 的完备性,即(句法上)对任意公式 p 和 ¬p ,两者之中至少有一个可由 S 证明,或(语义上)如果任何满足 S 的公理集 Γ 的模型也满足公式 p ,那么 p 可由 S 证明。在一阶逻辑中这两种定义是等价的。而图灵完备一般指的是某个特殊的计算模型(神经网络,元胞自动机,etc)具有和图灵机等价的计算能力,根据丘奇-图灵论题,这就意味着该计算模型是通用计算模型。

不过图灵的工作确实和哥德尔不完备定理有很深的联系。事实上,(经典的)形式系统作为一个我们有限的人类用以认识抽象世界的工具,需要满足如下两个条件:

(1)存在递归算法在有限步内判定某公式是否是形式系统的公理。

(2)存在递归算法在有限步内判定某个公式序列是否是从公理开始到某个特定公式的证明。

而满足这两个条件就意味着,形式系统S 中可证明的公式构成一个递归可枚举集 K ,同理 S 中可否证的公式(即可证明其否定公式)也构成一个递归可枚举集 K' 。现在自然的问题是:

(1)K∩K' 是否为空集。

(2)K∪K' 是否为(给定语言上的)公式全集。

如果交集不为空,那么意味着存在既被证明又被否证的公式,这就意味着S 是不一致的,而如果并集不为全集,那么意味着有 S 既没有证明也没有否证的命题,即 S 是不完备的。最好的情况下,如果 K 与 K' 恰好构成全集的一个划分,那么根据Kleene定理, K 将不仅是递归可枚举的,并且是递归的。这意味着存在一个算法判定一个命题是否是 S 可证的,并且由 S 的完备性,任何(给定语言上的)语句都可以由算法来判定真假。

哥德尔不完备定理告诉我们,两者不可兼得,因此(当S 包含初等数论时) K 的补集 Kᶜ 不可能等于 K' , Kᶜ 不是递归可枚举的。而图灵的工作则告诉我们,确实存在一个递归可枚举集,其补集不是递归可枚举的,这个集合就是停机问题的集合 H={n∈N| n n }。我们可以利用 H 的存在来证明哥德尔不完备定理。

首先证明停机集H 可以用某个初等算术公式表示,因为 H 是递归可枚举的,因此是某个递归函数 f(x) 的定义域(值域),而所有递归函数都可以在初等算术中由 Δ₁ 公式表示(并不容易,需要一些特殊的初等数论技巧,哥德尔定理的证明过程中有不少准备工作是关于这个的),因而 H 可由 Σ₁ 公式 ∼H(x) 弱表示(即如果 n∈H ,则 ∼H(ˆn) 在 S 中可证,ˆn 指n在形式系统中对应的常项)。

因为Hᶜ 不是递归可枚举的,因此集合 H'={n∈N|¬∼H(ˆn) S }和 Hᶜ不等。那么两种情况中至少有一种成立:

(1)存在某个自然数m,属于H' 但不属于 Hᶜ ,那么m必定属于 H ,如此 S 是不一致的。

(2)存在某个自然数m,属于Hᶜ 但不属于 H' ,那么m必定不属于 H ,如此 S 是不完备的。

数学联邦政治世界观提示您:看后求收藏(笔尖小说网http://www.bjxsw.cc),接着再看更方便。

相关小说

十二星座之星空璀璨 连载中
十二星座之星空璀璨
陌cc
当你仰望天空,星空璀璨,繁星闪耀,如此美丽的背后究竟是怎样的凶险和困境,才有如此漂亮的星空呢?星空之下隐藏的秘密又是什么呢?|星空如此璀璨,......
6.3万字2个月前
魇惡知境 连载中
魇惡知境
健力老登
俅谙与笙暮
1.2万字2个月前
异世中原 连载中
异世中原
上官青鹤
异世界日记
0.2万字2个月前
柔弱女主的封神之路 连载中
柔弱女主的封神之路
向天打月亮
柔弱女主觉醒后绑定了系统,一步步在诡异世界立足,达成灵魂与身体的双重逆袭
1.6万字2个月前
虚妄之国 连载中
虚妄之国
儚镜
如果在这个世界上,身边的所有人都否认一个你熟识的人的存在,且看不见她时,她找上了你,你该怎么办?是平行世界?亦或是自己的臆想?这个世界就是虚......
0.5万字2个月前
师妹修仙:笑闹青云间 连载中
师妹修仙:笑闹青云间
南山竹海^
本以为修仙之路严肃艰辛,可谁能想到竟有这么一位沙雕师妹,将整个修仙界搅得欢笑不断!看她如何在青云间摸爬滚打,凭借自己的无厘头和独特魅力,闯出......
2.2万字5天前