【数学】3x+1问题(4)

作者:异调

六、会不会永远证不出来

自从哥德尔发表了他的著名的不完备性定理以来,每次碰到一个十分 困难的问题时,数学家们就免不了疑神疑鬼——这会不会证不出来? 哥德尔的不完备性定理说,在包含皮亚诺的自然数公理的数学公理系 统中,总有不可证明的命题存在。公理系统的这种性质叫不完备性。

比如说,如果我们只取欧氏几何的前四条公理,那么平行公理是不能 用这前四条公理证明出来的,也就是说只有前四条公理的平面几何是 不完备的(这个例子不是很严格,因为欧几里德的公理系统在现代观 点下是不严密的,但是我举这个例子只是为了说明不完备性这个概念, 所以关系不大)。 所以说,如果我们只用皮亚诺的自然数公理,甚至再加上现代的集合 论公理系统,也有可能不能证明3x+1问题。甚至即使3x+1猜想其实是 错误的,我们也有可能不能证明这一点。比如说,我们可能发现一个 航班,我们对它进行计算,发现它飞得越来越高,但是无论如何不能 证明它永远也不会回到1上来。

当然无论什么数论问题都有可能搞得数学家们这样疑神疑鬼,虽然其 实是他们还没有发现证明。不过有一些蛛丝马迹表明我们有必要稍微 严肃点看待此问题,因为3x+1问题离不可证明的问题并不太远。 J. Conway(喜欢数学游戏的朋友可能会记起这个名字来,著名的生命 游戏就是他发明的)在1972年考虑了3x+1问题的推广形式。在3x+1问 题里,我们把数字除以2,然后得到了2种可能的余数(0或者1),按 照余数我们使用2个公式(除以2或者乘3加1)。Conway考虑了除以一 个固定的p,按照余数的不同(这时就有p种不同的余数)分别使用p个 公式的情况。然后他提出了一个类似“在1着陆”的猜想。他在论文中 证明了,这个猜想在集合论公理系统中是不可证的。

事实上,在任何一个包含了皮亚诺的自然数公理的数学公理系统中, Conway的方法都可以定义一个类似于3x+1问题的不可证命题。当然这 不是说有一个在所有公理系统中都不可证的命题。“不可证”总是相 对于某公理系统而言的。当然,Conway的方法并没有说明3x+1问题本 身是不可证的,也没有说它一定是很困难的(事实上有些3x+1问题的 变种是很容易解决的),但是这毕竟说明,有些很象3x+1问题的命题 是不可证的,这把事情搞得很可疑。 1993年,法国里尔(Lille)的基础信息实验室使用了Conway的方法来 演示一套基于逻辑规则的编程形式的威力。同许多数学中的例子一样, 先头看上去最没用的课题,会有很具体的用处。

七、各种变种

数学家总喜欢把问题推广,使它更抽象化和一般化,因为这样可以把 一种在具体某个问题上使用的方法的威力应用到一般的情况上去,从 而得到很有可能是出乎意料的结论。 数学家们首先考虑,如果把3x+1问题的规则运用到负整数上去,会产 生什么现象。他们发现了三个不同的循环:
1)-1→-2
2)-5→-14→-7→-20→-10
3)-17→-50→-25→-74→-37→-110→-55→-164→-82→-41→-122 →-61→-182→-91→-272→-136→-68→-34
他们猜想,这就是所有的循环,而所有的负整数都会掉进其中一个里。 他们还提出了5x+1问题,也就是在奇数的情况下用5x+1来取代3x+1。 这下又有好几个循环:

1)6→3→16→8→4→2→1
2)13→66→33→166→83→416→208→104→52→26 3)17→86→43→216→108→54→27→136→68→34
但是5x+1问题中的第7次航班好象老在那里飞啊飞,怎么也跑不到一个 循环里去,但是谁都不能证明的确如此。

上面Lagarias的那个启发式论证使得数学家猜想,如果q是大于3的奇 数的话,对于qx+1问题,总存在至少一个航程无穷的航班,这看起来 很象是一个“反3x+1问题”。 还有许多其他的3x+1问题的推广,一些结果把它们和其它数学领域联 系起来,比如说素数理论,某些丢番图方程(求解系数为整数的方程 的整数根,比如著名的费尔马大定理就是一个丢番图问题),马尔可 夫链(概率论中的递归理论),遍历理论(一种关于函数混合递归的 理论)。 就算3x+1问题终于被解决了,看看所有这些变种,也够数学家们自娱 自乐上几百年的了。

大学生数学竞赛题汇编
大学生数学竞赛题
高中数学联合竞赛试题
国际象棋中的趣题妙解
数学家俱乐部
数学趣题汇编
牛顿:在海边寻找贝壳的人
凯尔文:是上帝创造了生命,并且掌管一切
陆地动物能变成鲸吗
数学界的奇人妙事
趣味逻辑学问题

Conway: 游戏人生
有关孪生素数的一个有趣猜想
素数之恋-伯恩哈德·黎曼
等分布理论简介
数学家波利亚
物理学之神奇的数
鸟和青蛙
超级圆周率π运算器
数学难题汇编
3x+1问题(1)

此条目发表在数学分类目录,贴了, , , 标签。将固定链接加入收藏夹。