Monkey Test 遐思

给公司做了个Symbian Monkey Test工具,结果跑monkey test的任务就一起承担下来。
Monkey Test其实就是个随机输入序列。我想知道这个输入序列长度同发现bug的概率的关系。

现在,一个bug的引发需要一个输入序列串。当这个输入串长度是1的时候,就是说,任意一个随机输入都可能导致bug。这样的软件其实根本不需要测试,直接砍掉重练就好了。因此需要用到monkey测试的程序,一般来说他的bug都是隐藏较深的。假如引发一个bug的输入序列长度是L。则问题就是,一个随机生成的输入序列Input(monkey),它的长度Lm,与引发一个bug所需要的输入序列Input(bug)的长度Lb的关系。

这又涉及到一个问题,就是可能的输入集合。现在我们只考虑手机触屏的话,一台640*320屏幕的手机,触屏输入集合是18万之多。但是考虑到一般的软件都使用控件,而控件一般不会太小而导致用户点击困难,可以用最小能够点击的控件大小作为单位,把屏幕切分开来,每个单元作为一个可能的输入。这就大大减小了输入集合。我们以32*32作为单元的话,一个屏幕会有200个单元格。为照顾一般性,我们设输入集合拥有a个元素。则一个长度为Lm的随机输入串,其可能的组合有aLm之多。

现在我们要考虑的是,这样一个长串中,恰好包含了输入串Input(bug)的可能性。这是一个数列求和。
第一项是Input(monkey)的第0个输入开始恰好匹配Input(bug)的概率。
第二项是从第1个输入开始匹配的概率。但还需减去与第一项重叠的部分。也就是从第0个输入开始,和从第1个输入开始,同时匹配的概率。
第三项是从第2个输入开始匹配的概率。还需减去与第一项重叠的部分以及与第二项重叠的部分。然后再补偿第一、第二、第三项同时匹配的概率。
这样的求和非常复杂,并且是否可能出现匹配的情况,其实是受Input(bug)本身的影响。这里我们作为估算,忽略掉重叠带来的误差,最后会得到一个偏乐观的结果。
于是Input(monkey)恰好包含Input(bug)的概率

p < (Lm-Lb)*a-Lb

当Lm远大于Lb时,我们可近似认为Lm与发现bug的概率成正比。于是Lm增长一倍,则p增大一倍。
由于是简单的线性关系,在Lb不变的情况下,只需简单的增大monkey test的测试序列长度,就能尽可能多地发现bug。因此我们可以预期,当Lm足够大的时候,几乎可以把所有Lb < Llimit的bug都找出来。而这个时候,进一步增长monkey test的长度就变得无效了,因为如果找完了Lb < Llimit的bug,想找到新的bug,一定都是Lb > Llimit的,换句话说,就会导致Lb的增大,而正如我们所见Lb是处于公式的指数上的。增大Lm仅能线性增大找到bug的概率,而增大Lb却导致概率指数级下降,最终导致的结果就是进一步增大Lm却很难找到新的bug了。

既然知道这个道理,我想计算出monkey test大概合适的测试长度。得到最大化的利益。我们根据上述讨论,设a = 200。根据经验bug通常有一个Lb <= 3。则如果我们希望发现一个特定bug的概率超过90%,则有

0.9 < p < (Lm - 3)*200-3

则我们的Lm需要7.2M。假如按照我们常用的设置,一秒钟执行两次操作的话,需要跑超过41天。

这个绝望的估计结果主要原因是200个的输入集合太过巨大了。假如我们仅考虑手机键盘操作的12个键的话,我们可以测试到Lb <= 5,其需要测试的步数大概是220K,按照1秒两个操作需要测试约30个小时,这就在可行范围之内了。

[编辑]这里我仅讨论了想要发现一个特定bug的情况。这是由于我们不知道软件究竟有多少个bug,为保守起见,就按照最悲观的方案来。如果想讨论多个bug的情况,例如10个,则我们仅需令10个bug都找不到的概率降低到0.1以下,则发现每个bug的概率约为0.2。注意到这里其实是对数关系,面对指数级数,这个关系不会对Lm的长度有显著贡献。

0.2 < p < (Lm-3)*200-3

将Lm缩短3.5倍,也无非是从41天降低到九天,仍然是不可接受的长度。当然你会说可以增加同时执行测试的手机数量。但是一旦Lb步长增加1,则立刻就会发现这点缩短其实无意义。[/编辑]

由此也可见,monkey test对于过于复杂以及bug隐藏过深的程序几乎不起作用,如需稳定性测试需要另求他途。

初读康德

最近开始读《纯粹理性批判》,德文翻过来的文章读起来非常累。目前仅仅读了序言和第一章。感觉他的一些论断和我自己的一些理解有很大不同。

康德首先把知识分成先验的和经验的。然后又把理性思维分成综合的和分析的。在我看来,先验知识相当于数学中的“公理”,经验知识相当于公理所讨论的对象。综合相当于提出新的公理,而分析相当于从现有公理和定理中推导出新的定理。

为什么我把“公理所讨论的对象”归类于经验知识,是因为,所有理论讨论的对象,都是经验中抽象出来的实在。例如几何中讨论的点、线、面、体,如果没有生活在这个三维世界中,是万难提出来的,又比如自然数,正是“来自于自然”,高等数学的创造来自于对天体动力学研究的需求,等等。数学世界是如此,物理、化学等经验学科就更不必说了。那么先验知识究竟是什么?我认为先验知识是组合经验知识的能力,是从经验中抽取知识的能力。这种能力是天生就存在的。只是在接触到实际的对象之前,这些能力无法发挥作用罢了。

然后,康德希望讨论的是“纯粹理性”,也就是不包含经验知识的理性。当然,他讨论的问题是“纯粹理性”的“批判”,也就是如何验证、如何批判“纯粹理性”得出的结论是否正确这个问题。

由于仅仅读了第一章,我不知道他会如何展开他的批判。但是就我目前的思考来看,“纯粹理性”很可能是不存在的。我不相信不通过经验就能获得任何先验知识。当然,逻辑本身的结构存在于我们的大脑中,这本身是先验的。但是如果没有经验世界的刺激,这些逻辑构造不可能发挥任何作用,也不可能因此获取到任何知识。就如同我前面做的类比,先验知识是理论,而经验知识是对象。如果没有对象,理论缺乏必要的主语和谓语和宾语,本身就无法表达出来。

为什么连谓语都不能确定,我认为,人类所知的任何谓语,都是从经验中获取来的,不论是奔跑飞行这类具体的动词,还是综合、分析这类抽象的动词,如果没有经验世界,是绝对无法由人脑自发产生出来的,因为既然不存在谓词所作用的对象,则这个行为本身也无法成立。

用个计算机术语来说,“纯粹理性”就好象是“纯虚类”,里面的任何操作,任何对象,都是“模板的”,都是“未定义”的。在不使用经验世界的元素将其“特化”之前,抽象类是绝对不能“实例化”的。

我想,康德想追求的这个“纯粹理性”就是“上帝”。但我怀疑,“上帝”是否真的可以使用人类语言描述出来。如果把人类的纯粹理性称之为上帝的话,可以解释非常多事情,同时可以解释为何上帝真名是无法念出的。因为他必须是不包含任何经验知识的存在。而这种存在在人类世界是无法找到的。

借用老子的话来说,“道可道,非常道”。当“上帝”这个概念,用“上帝”这个名词表达出来的时候,它就变成是经验的了,于是失去了他的“纯粹性”,从而不是上帝。“吾不知其名,强名之而曰‘道’”。但是这个概念必须有一个名称,因此用“上帝”来代表他。我不知道康德的纯粹理性批判是否得出我的这个结论,我会抱着这些问题继续读下去,看看作者的意思具体是怎样的,而我的理解是否可以与他的理论相融。

 

圆周率绘图

自从翻译了维基上那篇BBP的文章一直想做这个用圆周率绘图的小程序。今天终于尝试了一下。可惜由于php的性能问题,没法绘出我想要的那种整幅的具有震撼效果的圆周率的外貌图。。。
目前只好用一个小小的24*24的小图先凑合着。其实BBP是个并行算法,要并行起来跑才会快的。但是php的多进程执行实在有点麻烦。所以准备以后有机会再来进一步做下去了。

图片正在加载,请等待

[感动]命运石之门

看了这个片子咱整个人都中二了。。
中二拯救世界的神作orz|||

Hacking to the Gate

咱貌似也泪点无限降低了。。这片子咱看到第三周目的时候,还没看完OP就已经内牛满面了|||

数十亿もの 鼓动の数さえ
数十亿的 心灵跳动
あなたには 瞬き程度の些事な等级
对你而言 不过是眨眼工夫的琐事
过去に囚われて  未来を叹くも
无论对过去的执迷 还是对未来的叹息
尘一つ 误算を许さぬ必然
皆是不准有丝毫误算的必然

『无限』に広がる梦も 描く未来も
『无限』膨胀的梦想 与理想的未来
仆达に许された 虚栄の権利
是我们应得 虚荣的权利
『有限』それは二つの 针が示す
『有限』那即是两根针所指示
残酷な约定と 选択へ
残酷的约定 与抉择
Hacking to the Gate!

だからいま 1秒ごとに 世界线を越えて
所以现在 越过每一秒的世界线
君のその笑颜 守りたいのさ
只因想要守护 你的笑容
そしてまた 悲しみの无い 时间のループへと
于是又再堕入 没有悲伤的时间回流
饮み込まれてゆく
逐渐被吞噬
孤独の観测者
孤独的观测者

命の主张と 无意味な证明
生命的论点 与无意义的证明
あなたには 退屈しのぎに足らぬ滑稽
对你而言是 就连消遣也不足以的滑稽
支配者きどりの 愚かな种族は
自称支配者 愚蠢的种族
うぬぼれた 稚拙な定理を并べた
自大地陈列 幼稚的定理

『无限』と信じた爱も 空の彼方も
『无限』爱的信心 和天空的彼方
仆达に示された 仮想の自由
皆是我们眼前 幻想的自由
『有限』それは无慈悲に 时を刻み
『有限』是让时间无情流逝
明日さえも否定する 选択へ
不惜否定明天的选择
Hacking to the Gate!

いくつもの 辉ける日々 仲间との约束
几度闪耀的日子 与同伴的约定
无かった事には してはいけない
不能就这样敷衍了事
そのために 时を欺く 残された仕挂けに
为此 欺骗时间 面对剩下的机关
もう迷いはない
不会再迷惘
孤独の観测者
孤独的观测者

だからいま 1秒ごとに 世界线を越えて
所以现在 越过每一秒的世界线
君のその笑颜 守りたいのさ
只因想要守护你的笑容
そしてまた 悲しみの无い 时间のループへと
于是又再堕入没有悲伤的时间回流
饮み込まれてゆく
逐渐被吞噬
孤独の観测者
孤独的观测者

人类智慧形态研究

上一篇讨论集合论的博客,我说会提出几个问题来支撑自己继续探索下去。而在归纳总结了自己的几个问题之后发现,多数问题是指向人类智慧形式本身的。

我在那篇博客中说,我认为集合论是一个企图解释全宇宙的终极理论。现在我改变了自己的想法。正好相反,集合论其实并非是解释宇宙的理论。解释宇宙这件事情,需要经验科学来完成。集合论其实是解释人类逻辑思维方式的终极理论。为什么我之前会认为,集合论有能力解释全宇宙呢?其实是这样的,首先,我假设人类有能力提出解释宇宙的理论,然后,集合论能够解释提出这个理论的人类的智慧的形式,并且能够构造出这种人类智慧形式所包含的全部知识。假如前提假设是正确的,人类确实能提出解释宇宙的理论,那么集合论自然能够涵盖这个理论啦。

因此这里提出的问题一就是,人类是否能提出解释整个宇宙的终极理论?

根据哥德尔不完备定理,任何图灵等价的构造都是不完备的,任何由可数无穷多个公理构造的定理集合都是不完备的。因此,假如说,人类智慧的形式其实是图灵等价的话,或者说,人类智慧所可能构造出的知识内容如果是可数无穷集合的话,那么,人类的理论体系很有可能是永远都无法完备的。但是,我相信,我们的宇宙应该是自洽的,因为“存在即合理”应该是凌驾于任何先验知识之上的经验公理。假如真的是这样,那么人类很有可能永远无法参透宇宙的奥秘。当然,其实这也是一个好消息。上帝、灵魂、地狱等等概念都有他们容身的场所,可以供那些“开天眼”,智慧超越人类可悲的知识集合的神棍们观测和研学。

所以这个问题其实归结为,人类智慧是否真的是图灵等价的?如果说是这样的话,马上就能得出一个结论,那就是人工智能一定能够成功。因为现代计算机就是图灵等价的。如果说人类智慧是图灵可计算的,则,只要随着科学的发展,早晚有一天能够用计算机创造出不可思议的智慧生命出来。硅基地球文明早晚将会诞生。

到目前为止,我倾向于认为,至少,我希望,上述两个问题的答案都是否定的。我认为人类智慧形式应该是超越图灵机的,并且,至少我希望,人类智慧能够无限逼近自然真理。同时,我不愿相信仅靠机械计算就能创造生命,无论那种计算模型有多么复杂,最终无非是确定有限自动机。

好了接下来我想问的是一个比较弱智的问题。就是,对于确定有限自动机而言,每个输入都有一个唯一的确切的输出。这样的构造是图灵等价的。假如,假如我给这个机械的模型加上随机参数呢?不是伪随机数,而是真正的随机数。举例而言,利用量子计算机的技术,对一个输入,有一定的概率产生一个输出,还有一定概率产生另一个输出。假如说自动机设计成这个样子,他还是图灵等价的吗?我在这方面没有做过研究,仅仅是初步想到他,所以不敢乱讲。我准备接下来查一些论文,看看有没有人做这方面的研究。
我看过一个量子算法,就是利用量子能够产生“真正的随机数”这个特性,来实现傅立叶变换,把时间复杂度降低了一个数量级。即使量子计算机的物理实现非常困难,其数学模型完全可以提前建立。因为利用到量子的地方,仅仅是他的产生随机数的能力罢了。我也知道在这个领域已经有前人研究了很多年了。我不清楚,是否量子计算机,仅仅给计算模型添加了真随机的能力,就能解决掉P = NP的问题。如果说真的是这样,这个世界未来的样貌将会是大大改观的。有可能,甚至要突破贝尔定律,知识爆炸的速度或许会以比指数还要快的速度疯狂增长。那个时候的人类智慧跟现在还会是同构的吗?或许还是。或许,人脑的计算模型就是如同量子计算机般充满了随机性的。这非常符合我们的经验。一个人刚做的决定,立刻就会后悔。同样的人有状态好坏之分,今天做得出的题目,明天就抓破头皮也解不出来。明明熟悉的老同学,嚼烂了舌头也想不起他的名字。这样的事情是很多的。是不是这就是因为,人脑其实充分利用了随机性呢?会不会说,带有随机性的自动机,比“确定有限”自动机所能表达的逻辑要复杂更多,是超越图灵计算能力的呢?
因为在这方面没有做过研究,所以不敢乱讲。这也是我接下来继续学习领悟集合论的一个重要的推动力。

另外我还有一个问题。就是,根据我的初步理解,似乎无论在自然数集合上做什么样的计算,都不可能构造出实数集合。无论是加也好,乘也好,乘方也好,自然数集合再怎么倒腾,到底还是可数无穷集合。所以我忽然觉得很奇怪的就是,实数,是不是真的实实在在存在的数呢?虽然说从古希腊就有人证明了存在根号2这样的数。可是这样的数毕竟是人脑构造出来的数。自然界中是否真的存在呢?

因为,实数集如果真实存在的话,哪怕仅仅是其中的一小段,例如[0, 1)的这样一个区间存在的话(这小小的一个区间其实等价于整个实数集),它包含的信息量都超过了全宇宙能量的总和。当然这是建立在,宇宙的大小和生命都是有限的这个假设之下的。我非常喜欢宇宙有限这个理论。在这样的假设下建立的宇宙模型简单而且容易解释。有着无限时间的宇宙,应该早就,在无穷早之前,就进入热寂了(熵不停增大直到极值的状态),有着无限能量的宇宙,也理应在无穷大的引力下崩塌;地球(如果存在)理应被从四面八方射来的无穷的星光灼烧成渣。
那么,如果宇宙蕴含的能量是有限的话,他蕴含的信息量是不是就一定也是有限的呢。或者至少是可数无穷多的呢。一个有限能量构成的基本粒子,假设他其实并不是“基本”的,而是其实蕴含着更大的信息量。假设他还是可以继续再分的。据我了解,物理学当前认为的最小粒子是夸克,并且据我所知夸克还没有被制造出能够独立存在的。我们暂且假设他还可以再再分,例如说,我们用半个宇宙的能量去轰击他,让他产生不可思议的巨大爆炸,也许在这持久的爆炸中,夸克乃至更小的粒子就能独立存在一段时间。我们继续用更大的能量去轰击他,用99%的宇宙能量,会怎么样呢?最终,我们用除了这个粒子之外的全部宇宙所含的能量去轰击他。没有更大的能量了。因为能够轰击一个粒子的能量最终是有限的,所以粒子可分的等级,应该就是有限的。更小的等级,在当前宇宙是观测不到的。我个人还是倾向于经验主义,观测不到的物理量应该就是不存在的。至少他对当前宇宙没有任何贡献,因此存在与否是没有意义的。同时,全宇宙所有粒子的总和一定是一个有限值。那么由有限个粒子构成的集合,其中每个粒子都是一个在有限步骤内就会定义完毕的有限集合。他们在每个时间点上都具有有限的信息量。因此最后,就差一个量可以决定宇宙信息量的基数,那就是时间。假如时间是量子化的,存在不可再分的最小时间间隔,那么这个宇宙的总信息量就是可数无穷多的。假如时间是连续的,总能找到两个时间点之间的时间点。那么,宇宙就是连续变化的,它虽然在每个特定的时间点无法包含无穷的信息量,但只要乘以时间这个维度,就立即包含了无穷的信息量了。
为什么上述讨论中只用到时间这一个量,而不说四维时空呢?在我看来这里时间和空间是等价的。假如时间固定,每个粒子在空间中的位置(三维坐标)都是固定的。当然,存在很多“实数”坐标值。但这些实数的数量却是有限多的(因为粒子的数量是有限多的),因此,这些实数的坐标值其实是可以跟一个有限集合内的元素一一对应的,只是他的物理含义不相同而已。只有当时间可以连续运转的时候,才有可能让一个运动着的粒子沿着一段曲线运动,从而产生出与实数集基数相等的那么多个三维坐标点。

因此,空间的连续性和时间的连续性其实就是等价的。假如说,虽然时间是连续的,但是空间却是量子化的,在每一段连续的时间点上,一个粒子都呆在原地不动,直到另一个时间段,他忽然“跃迁”到下一个空间坐标上去了。假如是这样的,假设存在连续的时间就没有意义了。因为你没有办法观测到他。在一次的,我用奥坎姆剃刀剔除不可观测的额外假设。

因为对当今的物理学发展并不十分了解,我不知道是否证实了时间的连续性。因此这里作为一个问题放在这里吧。

这个问题其实是深深刺入宇宙本源的。因为,假如时空真的如我上述讨论,是量子化的,则宇宙其实就是一个自动机!那么很有可能,他就是图灵等价的!如果真的是那样,那么宿命论就是真的。当然,这里还有一个悬而未决的问题,就是量子计算机能否让计算机突破图灵可计算的边界。但是,进一步的,假如时间是量子化的,但是真随机有限自动机超越图灵,至少我们可以制造真随机有限自动机来模拟宇宙。同时,真随机有限自动机将成为真正的人工智能!因为,宇宙是真随机有限自动机等价,所以宇宙能够创造出来的生命,量子计算机就理应能够(在有限时间内)将生命(不仅仅是人工智能,而且他还是货真价实的生命体)创造出来。

哇,看来集合论果然是必须要学的重要学科啊!!很有可能他就包含了宇宙的真理哟!

集合论研学初心

最近在网上看了几位大牛的博客,对集合论逐渐产生兴趣。进而去维基上翻了翻,对集合论有了个初步的了解。这里做点笔记。

集合论是一个目标统一全宇宙的超级理论。当然也有可能他统一不了了,但透过集合论,去理解人类逻辑的固有定式,去理解数学如何解释世界,是很有意思的事情。

朴素集合论是很容易理解的事情。首先有元素这个概念。然后元素可以属于集合。两个集合相等完全由其元素一一相等来判定(外延公理)。然后集合的元素也可以是集合,集合可以为空(空集公理)。
这就是高中课本上的集合定义了吧。但这样的定义存在巨大的问题。

例如著名的罗素悖论:设存在集合R, 它包含的元素由对“所有集合”应用的一个函数(谓词)来确定,即“不包含自身的集合”(固有前提,该元素是一个集合)。这个谓词是合理的,因为在”所有集合”这个范围内确实存在不包含自身的集合。那么,将所有这样的集合作为元素,放到这个集合R里,理论上似乎可行。那么我们看这样的集合R有什么特性呢? 他或许不包含自身(R不属于R),如果是这样,那么他就应该包含R(因为R是所有不包含自己的集合嘛)。但是如果他包含了自己,他立刻就不应该包含自己了(包含自己的集合不应该属于R)。

为了阻止这种情况发生,严谨的集合论不得不增加一些公理和概念来回避这个问题。首先,使用一个谓词确定的集合不再确保构成一个集合。他们只是属于一类(内涵公理替代公理)。因此“”这个概念比集合更广泛。如果一个类不是一个集合(例如“不包含自身的所有集合”),那么他就是一个“真类”。
另外,在一个集合上使用一个谓词仍然可以得到所有符合这个谓词的元素的集合。这称之为分类公理
之后引入“正则性公理”来确保集合的合理性。这个公理描述起来有点费力。首先,公理化集合论一般认为所有集合都是集合的集合,不存在集合之外的概念。集合的元素也是集合(有可能是空集,所以这个定义是可以终止的)。然后正则性公理是说,任意非空集合,总存在一个元素,这个元素(同时也是集合)与这个集合的交集为空。这样理解很困难,我们反过来理解。任意非空集合,不可能发生这种情况:他的所有元素都与其相交。这仍然很难想象,我们举个例子来观察这样的集合的特性。
假设R符合这个条件,假设他包含一个元素。则 R = {A}
这里A和R相交非空,则A交R = B
B是A和R的交集,则B是R的子集。同时B非空。则B只能是{A}。也就是说,B = R。
所以A交R = B。A = {A, …}
而R = {A}, 所以R = {{A, …}} = {{{A, …}, …}} = {{{{A, …}, …}, …}}
这样的A是无穷递归定义的。或者说,在有限时间内无法写出R的定义。这和无穷集合并不相同。无穷集合只是在有限时间内无法写出这个集合中的元素而已。如果一个集合无法被定义,我们应该认为他就是不存在的吧。
R包含更多元素的情况比较复杂,不过归结到最后都是如这样形式的无穷递归。可以说这个公理防止了这样的不良定义的集合出现。所以“禁止自包含”就是正则公理的内涵之一。

以上几个公理定义了集合的内涵和外延,以及一个操作(分类)。接下来还需定义集合的并(并集公理)这个操作。这个操作的定义与朴素集合论中的定义略有不同。
这个定义的形式描述有点绕,这里形象的说明就是:一个形如R = {{A},{B},{C}, …}的集合,他的并U R = {A, B, C, …}。
所以,{A, B, C}U{D} = U{{A, B, C},{D}} = {A, B, C, D}
相信读到这里很多lisp玩家已经感到似曾相识了。确实函数式语言、图灵机等等计算机科学基本概念都可以说是自集合论派生出来。这也是我会忽然跳这个大坑的原因。

定义了并之后,集合操作基本定义完全。至于说交集这个定义呢,因为存在分类公理,交集其实是分类公理使用“属于某个集合”这个谓词的一种特化形式。因此无需使用公理定义出来。
还有几个公理,我这里配合描述集合论构造自然数的定义来描述。因为这一段似乎是集合论中最容易懂的一部分了

这里直接给出定义的形式,他比描述还容易懂。之后根据这个形式中出现的几个特征,引出几个定义。

0 = {} (空集)
1 = {0} = { {} }
2 = {0,1} = { {}, { {} } }
3 = {0,1,2} = {{}, { {} }, { {}, { {} } }}
4 = {0,1,2,3} = { {}, { {} }, { {}, { {} } }, {{}, { {} }, { {}, { {} } }} }

由于自然数是无穷的,必须使用归纳法定义全体自然数。前面集合的并集的定义是一个铺垫:
首先 0 = {} 是自然数。
然后 假设x是自然数,则x的下一个自然数x’ = x U {x}

由是自然推出了元素的“后继”这个概念。x’是x的后继,则x’ = x U {x}。并依据后继这个概念定义归纳法(无穷公理):
存在集合A,首先,空集属于A,并且对于任意的元素x属于A,则x的后继x’ = x U {x}也属于A。
这不破坏正则公理,因为空集属于A。因此A中存在一个元素,{},他与A的交集是空。
这并不是文字游戏。要求空集包含于A是非常重要的。这相当于是数学归纳法中的初始条件。否则归纳法无法成立。

此外还引出了集合中元素的顺序问题。称x’是x的后继,就是说,x和x’之间存在顺序关系。并且这个顺序关系可以传导。也就是说,x1是x0的后继,x2是x1的后继,则x0和x2也存在x0在前, x2在后这样的关系。 通过这个关系,可以得出集合的序的概念。

首先定义良序集合。所谓良序集合,通俗地说,需要符合两个条件。其一,首先给定一个判定关系的运算符,任意举出这个集合中的两个元素,在这个运算符上能够判定顺序关系(因此这是一个线性的顺序关系,每个元素如果有,都仅有一个后继和一个前驱);其二,任意给定这个集合的子集,能够找出该子集的最小元素(无需保证最大元素)。符合这个条件的集合和这个关系一起就称作良序集。因此自然数在<=这个关系上是良序的。但是整数在<=这个关系上就不是良序。因为不存在这个集合的最小元素。但是如果用其他的顺序关系运算,仍然可以给出一个良序的整数集。例如0, -1, -2, ..., 1, 2, ... 这个顺序,0最小,然后负数比整数小,然后绝对值小的数更小,则得到一个良序集。为何一定要确保最小值,其实就是为了使归纳法成立。后续的大量论证将会建立在良序集的归纳法之上(超限归纳法)。

好了,对于良序集,既然后继是唯一确定的,就可以不停地向后列举下一个后继。如果这个集合是有限集,则最后一个后继的序号(序数)就是一个自然数。如果是可数无穷集合,则这个最大的序数无法在有限时间内获取到。我们设这个数为ω (自然数的序数)。仍然存在序数比ω还大的可数无限集合。例如整数,假如按照上述排序方式,则其序数相当于是ω+ω。又比如,自然数如果采取另一种排序方式0, 3, 6, 9, …, 1, 4, 7, …, 2, 5, 8, …则自然数的序数是ω+ω+ω。我们看到,序作为衡量集合大小的指标有一个不足,就是序是由一个人为确定的关系运算符来确定的。关系不同,就有可能改变序大小。因此还需要更通用的,仅与集合本身相关的指标来衡量集合的大小。

接下来应该引入基数的概念。但由于这一块我还没有完全理解,所以暂且写到这里了。

后续会写一篇文章记录读到目前为止我的各种疑问。作为思考题,推动自己接下来继续去学习~
引用:
维基百科:公理化集合论
刘未鹏:永恒的金色对角线
Matrix67:对角线方法之后的故事

简朴节约编程

我听说,代码行数越少,出错概率越小。

如果不管什么逻辑都只写成一行代码的话,岂不是只有一行代码的维护成本了!
所以。泛用逗号表达式吧!泛用:?吧!泛用参数求值吧!
至于命名规范,越减省越好。善用26个字母+大小写,基本够了。配合大括号屏蔽和::引用,绝对够用~
实在不行就后排序号嘛。再不够用,把变量全存储在一个数组里,直接下标引用。注意类型转换哟,数组里第一个变量是int,第二个变量也许就是字符串了。
这样存数据,连复杂类型都省了。管他啥东西还不都是字节啊。直接紧排在内存里,还省空间,连内存对齐的问题都不必考虑了。
更不用提动态内存管理了。所有数据全堆在静态数组里。想要空间自取就好。

这样一个工程在一个文件里写完就可以了。头文件都省了。更不用说压缩软件了,源码文本打开就是满满的各种字母符号,信息量满满,没有压缩空间哈哈。

什么?你说这代码不好维护?

这样的代码还需要维护么。。。出了bug重写一份就好了嘛!

utf-8编码研学

好久好久没有更新博客了。登录密码都是输了四五遍才输对。

最近写了挺多邮件。相对的,好像某处倾泻掉了一样,就没心情在博客上码字了。于是今天依旧是灌水的短篇吧。

最近被utf-8搞得各种头痛。差点就要练出肉眼看二进制编码的火眼金睛。先举个今天遇到的小问题吧。
java用gbk方式写入的文件,似乎有个特性,是会自动把gbk编码中不能识别的0x0这个字节,替换成”?”,也即0x3F。这原本也没什么,但当他读取utf8文本并重新写入新的文件的时候,就会出现偏差。
众所周知,utf8编码的英文和符号部分是同ASCII编码兼容的。同时,在大多数中文中,很少出现0x0这样的字节。因此,用ASCII硬写utf8编码的中英混合文字,然后这个文件再用utf8的方式打开,运气好的话居然可以侥幸蒙混过关,毫无错误。然而,一旦文字中出现了带有0x0字节的utf8编码,就没那么侥幸了。
例如“个性”的性字,其unicode编码为0x6027, 翻译成utf8的话:

性
 60	    27
 01100000   00100111
[1110]0110 [10]000000 [10]100111
 E6	    80	       A7

这里用方括号标识了utf8的字节头,方便辨识。在windows上是使用小端序,所以实际的序列会是这样:

0110 1110 0000 1000 0111 1010

这里第三个字节出现了0x0,悲剧发生了,被java的流输出不知怎么就那么智能替换成了”?”

0110 1110 1111 0011 ...
6    E    F    3

结果这里就乱码了。打出来内容一团糟。变成“个<E6>?”。

另外一个曾让我头疼一天的问题,就是根据utf8编码规则,并不会出现0xC0 0x80这个双字。因为如果按照编码规范

 0xC0           0x80
[110]0 0000    [10]00 0000
 0000           0000

这根本就是0x0嘛!不可能编码成这个样子的。wiki上查了半天才发现,原来这个又是windows的专有解决方案。完全是windows系统一厢情愿,想要区别于一般的ASCII文本而作的别扭事。结果这样的文本想要插入到mysql数据库时,就会被数据库认为是不合理的utf8编码而被冷冷拒绝!
所以整理utf8的编码问题,有时候还是要一直看到二进制上面来,这样问题发生在哪里也就会比较清楚,该怎样解决就不再像是霰弹枪编程,左试右试都不知道哪里出错了哟。

当你看着自己的作品

好不容易码完代码,修掉几个显而易见的bug,经过调试终于呼哧呼哧的运行起来了。
磨一杯咖啡,坐在机器面前,欣赏着自己的杰作,那有条不紊地输出的一行行日志,那一处又一处精巧的设计。避开各种陷阱,走在平稳有序的大道上。

这往往是刚刚写完代码的初级阶段。

随着咖啡逐渐冷掉,失去醇香和温度;随着输出的日志逐渐变得混乱:乱码和未截断的文字扭结,触目惊心的[warning]和[error]纵横,过量来不及查看的惊叹号飞掠屏幕;随着自己思路逐渐冷却,意识到更多没解决的隐患,发现自己的设计远远不符合需求,框架仅仅是个演示用的玩具,早晚得彻底重构。随着这些烦乱的到来,机器面前的程序员再也坐不住了。呼哧呼哧的不再是运行着的程序,而是程序员的粗喘。再也不想面对这团乱麻,一口咽下最后半杯半冷而苦涩的咖啡,回味这过期的香醇。

这可以算是中级阶段。

当吃完不知是夜宵还是早餐,啜饮着清香的橙汁,随着东边逐渐泛起霞光,思路逐渐澄澈;当提交完代码,把整晚的工作缩减为一句简短的ci message;当整理自己发现的几个缺陷,计划好新的issues;当把这些都做完,忽然发现自己原先的惊恐万状全是愚蠢,几个“重大bug”,无非增加几条异常处理就可以搞定;原本想要做的全盘优化,其实只需在某个函数做个小改动,就能得到70%的效果;说是要重构,其实即使现在这样也无可厚非,今后的扩展性完全可通过函数指针和类继承来得到。如此一想,被自己的怀疑、惊惧扭曲成的一个毫无希望的无聊玩具,又转眼间变成前途光明,不过仅仅有几处bug的精巧框架了。

这就又回到了初级阶段。

于是就继续编写代码,崩溃,调试,绝望,然后又希望。

如此循环往复。

也许有一天,当看着自己的作品,心中静如止水。程序的功能既不多也不少,既没有令人匪夷所思的神奇之处,也没有不该有的缺陷。该完美的地方稳定地每次都是完美。该有缺陷的地方每次都按照计划产生缺陷。程序的行为完完全全符合预期。当你看着他,既没有期望,也不会失望。

或许到那一天,才可以算作是高级阶段吧。

万智牌经典赛事-2009世界冠军赛

最近玩万智牌近乎痴迷。看了一场比赛录像。薪传赛实在看起来累,光是英文解说听得半懂不懂不说,牌手用的牌没一个认识的。不过借助牌表数据、grep和python等强力工具,加上在线卡牌数据库,咱终于通过模糊视频里面残缺的信息和解说提到牌名字的大概发音,把一局比赛的主要过程了解清楚了!

T1.5 – Legacy
link: 视频: 万智牌2009年世界冠军赛,中国国家队夺冠!
Li Bo (China) vs. Benjamin Rozhon (Austria)

比赛的初期,Li使用两张Daze解掉了Rozhon的Top

Daze Sensei’s Divining Top

之后Bo放进了Cursecatcher以及jitte大肆进攻

Cursecatcher Umezawa’s Jitte

我看到Li手里还有人鱼领主和易形地窖

Lord of Atlantis Mutavault

而另一边,放了几个法术并且死了几个生物的Rozhon正在谋划一个秒杀对手的阴谋。他的手里有Dark Ritual, Cabal Ritual等法术力源。同时,藏在他手里最后一张,仅仅露出一个角的Ad Nauseam,居然被眼尖的解说一眼看到。

Dark Ritual Cabal Ritual
Ad Nauseam

他的墓地目前有5张牌。距离Cabal Ritual的门槛仅有一步之遥,而这个时候他打出了Ponder。

Ponder

这张Ponder他Ponder了好久。解说都吐槽他说:”he’s still pondering his ponder.”

之后他打出Thoughtseize,确认对手最后留存的反击手段。

Thoughtseize

这样Cabal Ritual的门槛达成,蓄谋已久的行动终于展开。等待Li装备了jitte的Cursecatcher攻击并获得2个充电指示物之后,Rozhon展开了行动。
他首先打出一张Lotus Petal。然后是Cabal Ritual, 使用掉他仅有的两张地。之后打出ad nauseam。这消耗掉他的全部法术力。
使用ad nauseam他展开了漫漫的翻牌顶之旅。
在他的牌库中他放入了大量Lotus Petal, Mox Diamond和Chrome Mox

Lotus Petal Chrome Mox
Mox Diamond

因此他得以不消耗生命就能重复使用Ad Nauseam。当然还有地。注意地也是0费。
他同样翻出了更多的Cabal Ritual,Thoughtseize以及Brainstorm

Brainstorm

但只有法术力和抓牌是远远不够的。牌组还需要一个制胜关键。而这个制胜关键也在他重复使用Ad Nauseam消耗掉他所有生命值之前就找到了,那就是Tendrils

Tendrils of Agony

依赖于Tendils的storm效应,只要能够在这个回合使用超过10个咒语就能获得胜利。而通过Ad Nauseam找出的0费咒语和法术力源给了Rozhon充分的补给,他总计释放了14个咒语。最后终结比赛的Tendils造成了28点伤害,并吸取等量的生命。

呜好累。终于把这局比赛的主要流程研究清楚了。2009年最终中国队取得了胜利,一组三位选手分别同时进行了薪传、特选和标准赛制的比赛。可惜的是视频转播的三个赛制比赛中的片段,都恰恰是三局两胜制比赛中中国队失利的那一局,没能看到我国选手如何施展套牌优势并取胜的风采。但至少通过前面的概观,可以知道Li Bo使用的套牌思路,是一个纯蓝控制,配合鱼人领主和十手的快攻打法。还有易形地窖这种变人地来保证输出。

呜越来越痴迷了,坑死爹了orz|||