机器困境

二十世纪初，以希尔伯特为首的一批数学家展开了一场空前的数学形式化努力，并试图为全部数学构建起坚实的逻辑基础。他们努力的目标就是要实现这样一个数学家们一直梦寐以求的理想，那就是宇宙万事万物的规律都可以化归为数学表述的形式，而全部数学则又可化归为严密的逻辑形式化系统。但令人意外的是，所有这些努力的结果却事与愿违，事实无情地宣告这一梦想的破灭。数理学家们终于认识到了逻辑系统的局限性。

对于一组公理及其形式系统能够容许比人们预期多得多的语义解释，而这些解释具有本质上的不同。也就是说，用公理形式系统描述的事物对象既不可靠也不唯一，公理系统根本没有限制解释模型。这就意味着数学真理性（由此推及客观真理性）不可能与公理化描述完全一致。

计算能力的限度

由于直接受到哥德尔定理的影响，1936年，英国年轻的数学家阿兰·图灵提出了一种被人们称为图灵机的理论计算机模型，就是为了寻找计算机器的极限能力的。

现有理论表明，任何计算装置，包括理论模型和实际机器，其计算能力均不大于图灵机的计算能力。如果我们规定带上的符号仅由“０”和“１”两种数字组成并约定ｎ＋１个“１”连写表示自然数ｎ，而用“０”（不管连写几次均作为一个看待）来作为数与数之间的间隔符，那么同样可以证明任何计算装置的计算能力均不大于这种自然数上的图灵机。也就是说，任意一个可计算的问题，使用编码方法，都可以对应为相应的一个自然数上的图灵机。

那么是不是所有的问题都是图灵机可计算解决的呢？根据上述说明，这个问题可以归结为是不是所有的自然数函数都是可计算函数呢？也就是说存在不存在图灵机不能计算的自然数函数呢？回答是肯定的，因为确实存在着图灵机不可计算的自然数函数。如果设fi（x）为所有自然数可计算函数，那么通过

                              g(x)=fx′ (x)+1 

导出悖论，就可以证明存在不可计算函数。