歌德尔和罗素 （3）烧脑的实例

用＂A certain integer g is not a prim number”

本身来说明小歌的证明，总带有一些神秘色彩：）

https://bbs.wenxuecity.com/teatime/746118.html

 

小歌（Gödel ）在他的证明里实际用到老康（Cantor）的对角线方法。

老康用对角线原理证明了 0到1 之间实数的数量 多于全部正整数的数量。

这个推论使我年轻时对老康的集合论 顶礼膜拜：）

 

用老罗（素）的基本原理可以定义出一类函数叫

＂primitive recursive functions “.

从计算上看，这类函数一定会在有限的时间内得到结果。

如果我们限制到用一个整数计算另一个整数，他们就会像

F(n) = 0

F(n) = n

F(n) = n ＊n ＊n

…

这类函数应该有无穷无尽的多。

但是原则上，因为这些函数的＂形式＂都是固定的，

我们总可以按公式的形式给他们编上号。

比如上面所列函数可以表达成

G(0，n) = 0

G(1，n) = n

G(2，n) = n ＊n ＊n

….

G就是F，但多了一个小歌的＂prim number”.

 （多重眏射，把公式编号：）

 

小歌问了一个问题：

是不是所有这类＂primitive recursive functions "都有”prim number “?

 

答案是否！ 小歌构造了一个 函数，但它不可能有＂prim number”!!!!

 

这里小歌借用了老康＂对角线＂，定义了一个M(无门)函数

M(n) = 1 + G(n，n)

即 M(n)的答案就是 相应的 G的 ＂对角＂（n，n）的答案 加＂1 ＂。

这个函数是从己知函数推出的，但肯定没有＂prim number “。

因为假设它有的话，比如＂x＂，那么

M(x) = G(x，x)，这跟＂ 1 + G(x，x) ＂矛盾：）

 

回到了 ＂A certain integer g is not a prim number”，

我们有函数＂g ＂，但它没有 ＂prim number “.

 

再次谢谢网友的提示

 

我好像理解了。prim numbers可能和primitive recursive functions有关。 

 

来源: youdecide 

参考资料：）特别是 Limitations 部分

https://en.wikipedia.org/wiki/Primitive_recursive_function