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

字面上说这两个关系不是很大：哥德尔不完备定理中的完备是指形式系统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://tongren.me），接着再看更方便。