当前在线人数5378
首页 - 博客首页 - 老梁博客 - 文章阅读 [博客首页] [首页]
0.999...、P/NP及数学证明
作者:niuheliang
发表时间:2018-10-26
更新时间:2018-10-26
浏览:785次
评论:0篇
地址:2607:fb90:276f:f99:3.
::: 栏目 :::

快周末了,不厌其烦码个贴科普一下如何证明0.999…=1。这个简单的初等数学问题之所以重要,是因为如果你会我写的这个用集合论证明的方法,理解P = NP就不难。根据我的观察结论,99%的数学博士、计算机科学博士对这个问题只是采取接受的态度,道理其实糊里糊涂。事实上,这个证明是从P = NP的证明里演化出来的。所以不难想象,为什么“如此简单的”P = NP证明“没有人想到”,即使读到了也可能不能理解。

首先,0.999…=1是更复杂问题的一个初等特例。可以用高等数学的方法予以证明。但这些高等数学的方法是怎么来的,怎么被承认有效的,其实还是从无数0.999…=1这样能被其它基础的方法予以证明的特例来的。而最基础的方法就是集合论,如等于是如何定义的。0.999…=1和P = NP,注意了,都是等于。当然,除了等于的定义,两个问题都需要一些背景知识,如算术运算或图灵机运算,假设定理证明机器人懂这些背景知识。

如果两个对象(集合)的所有属性(成员)都相等,则我们定义这两对象(集合)相等。注意,这个是定义是公理。如果不同意这一点,则没有继续讨论的必要。这个公理在物理上也在用,例如你无法区分两个粒子,则这两个粒子就是全同的。所以有人说世界上只有一个电子,所有我们观察到的只是它不同的像。等价于数学的不同分支,就是基本原理不同的表现。另外,在等于中我们要用到集合论的另一个基本概念,一一对应。这也是一个公理,如果不同意,没有讨论的必要。注意,我们不需要无穷这个概念,在等价问题P = NP里能深刻地看出来为什么没有无穷的位置。

第一步:证明1/9=0.111...。也就是说,1/9的十进制展开小数点后每一位都是1。这一步可以用数学归纳法证明。大致是证明第一位是1向后传递的余数是1;如果第n位是1余数是1,则第n+1位是1余数也是1。

第二步:证明0.111...和0.999...每一个1和每一个9一一对应。

第三步:定义算术运算,9个1加起来等于9。所以我们有9个0.111...加起来等于0.999...。这里要用到算术和等于的定义。每一个1加9次就是一个9,也就是9个0.111...加起来每一位都是9。根据一一对应和等于的定义9个0.111...加起来等于0.999...。

第四步:就是基本的算术问题。以及等于关系是传递的。0.999…=0.111...x9=1/9x9=1

如果没有记错,几年前那篇P = NP预印给出了一个类似的定理。给定一个图灵机和*任意*一个它接受输入到整数集的测度(如图灵机接受某个输入需要的时间),以这个测度定义这个图灵机接受语言L(m)的子集L_i(m)为所有输入的测度小于等于i的集合(如L_1(m)在上面时间测度下就是只用移动1步就停机接受的子集)。则L(m)等于“所有”L_i(m)的合集。注意,如果把L(m)看作1,L_i(m)对应到小数点后第i位的9。则同样是一一对应问题,不失一般性,这两个定理其实相似/等价。

这个图灵机给出的定理回答了很多人对“无穷”的困惑和疑虑。很多人弄混了无限(unlimited)和无穷(infinite)。一方面,需要无穷步骤资源的运算超越了图灵机/计算的能力。另一方面,在这个等于问题上,不需要无穷和无穷的计算能力。这也是我严格区分无限和无穷两个概念,说无限(制)的问题但不需要无穷能力这个感悟的由来。这几句话可能很绕。想不明白的可以跳过。如果你觉得自己明白了,接近1的概率(或者时髦一点根据我们讨论的等式就是1的概率)你不明白。因为我都没想好如何用有穷的文字描述这个涉及无限可能的感悟。

举一个具体的例子。一个数学问题可以涉及无限制数量的子问题(如无限多的9),但(可能)存在不需要无穷资源的证明。如果需要无穷资源,这个问题其实就是不可证明/讨论的。当然,不是所有涉及无限制数量的子问题都存在有穷资源的证明。根据上面图灵机语言的定理,这个测度为整数集(可数集)就存在有穷资源证明。如果不是整数集,正如昨天有人说的,不可数个不为零的正整数的和发散(不存在有穷资源证明/计算)(数学里收敛一个“不为人”注意的前提)。其实道理一样。

最后,如果你耐着性子读到这里,没破口大骂扬长而去,发两个彩蛋:

1、证明是一类问题,能力和求解没区别。你证明了0.999…=1和算出0.999…=1结果没有区别。注意证明0.999…=1是NP的思路就是你猜到结果可能等于1,然后验证出来。而计算0.999…=1是P的思路。P = NP的意思就是每一个在P时间内可验证的问题都在P时间内可计算。上面的证明利用了等于的传递性,把计算0.999...通过等于一一对应地转换成了其它问题/算法/图灵机,然后用有限的资源完成证明/运算。

2、根据P = NP的“证明”,任何数学猜想的证明(验证是否相等),都是数学家有意无意地在寻找(新的)测度,通过这些测度把无穷可能的子问题转化为有穷的证明步骤。

3、P和NP的关系可以简化为1和{0,0.9,0.99,...}这个集合的关系。如果1属于{0,0.9,0.99...}则P = NP。

可数集是人类接触最多的集合。定义了人类当今的能力。不可判定、不可计算、黑洞、量子测不准,归根结底就是可数的限制。非可数的纯数学/逻辑/物理世界究竟怎么样,我需要糊口推娃,还没有精力研究。哪位有兴趣提供软饭的,欢迎联系。




提示: 本博文来自于 Military 版

[上一篇] [下一篇] [发表评论] [写信问候] [收藏] [举报] 
 
暂无评论
 
用户名: 密码:
发表评论
评论:
[返回顶部] [刷新]  [给niuheliang写信]  [老梁博客首页] [博客首页] [BBS 未名空间站]
 
Site Map - Contact Us - Terms and Conditions - Privacy Policy

版权所有BBS 未名空间站(mitbbs.com) since 1996