(转)趣题:随机选取两个无穷大的图,求两者相同的概率趣题:随机选取两个无穷大的图,求两者相同的概率

http://www.matrix67.com/blog/archives/2168

图灵机vs数学家——图灵机计算能力的分析

这里我尝试回答两个问题
0.是否存在数学家可以做出判定的问题,不存在判定该问题的图灵机?
1.是否存在这样的通用判定图灵机,输入任何数学家可以判定的问题,该图灵机都能在有限步骤之内输出其判定结果,而不输出任何错误的判定结果?
2.是否存在这样的自动判定图灵机,自动尝试判定所有可能的判定问题,而对于其中任何一个数学家可以判定的问题,该图灵机都可以在有限步骤之内输出其判定结果,而不输出任何错误的判定结果?

现在我们对数学家做一个假定:只有能够完全形式化的有限判定过程,才会被数学家承认。
这个假定是合理的,虽然天才的数学家可以用直觉、灵感、做梦、神启等等各种惊人的手段获得一个问题判定结果,但只有能够被彻底形式化的有限判定过程才会被认为是可靠的判定过程。换言之,任何一个能够被数学家认可的判定过程,绝对不能包含任何直觉成分。

上述假定蕴含这样一个结果:
能被数学家承认的任何判定,其步骤数目必然有限。
能被数学家判定的任何问题,其符号刻画必然有限。

有限符号可刻画的问题的全集显然是递归可枚举集,因为它是所有有限长字符串集合的子集,因此可以用自然数i进行编号,记为Pi。
同理,刻画任何有效判定过程的符号串长度必然有限,因此显然是递归可枚举集,也可以用自然数j进行编号,记为Dj。
任何形式系统的推理规则,至多属于乔姆斯基无限制文法的子集,因此推理规则所生成的语言必然是递归可枚举语言的子集,而递归可枚举语言是图灵机可接受(但未必可判定)语言。所有形式系统的推理规则,都可以用自然数k进行编号,记为Lk。

判定【Dj是否为Lk的问题Pi的有效判定过程】,可以用一个通用验证图灵机V(Lk,Pi,Dj)进行判定,而且这是个可判定过程。因为Lk中任何一个判定过程中的任何一个步骤否有效,可以直接套用Lk的推理规则进行判定,而由于整个判定过程的步骤必然有限,因此整个判定过程Dj的有效性必然是可以被图灵机V判定的。

现在我们来构造一个图灵机H(Lk,Pi),对于给定的形式系统Lk以及Lk的问题Pi,如果Lk中存在对Pi的有效判定过程Dj,那么图灵机H就输出Pi在Lk内的判定结果。但如果Lk中不存在对Pi的有效判定,H永不停机。

为了构造H,我们先考虑一个不可行的构造,然后将其改造为可行的构造:
构造无穷多图灵机Hj(Lk,Pi),其定义为V(Lk,Pi,Dj)。显然,如果存在某个j,Dj是Pi在Lk下的有效判定,那么Hj必然在有限步骤内停机。
如果将所有的Hj同时启动,那么只要问题Pi在Lk下可判定,那么至少有一个Hj会在有限时间内输出判定,除非问题Pj在Lk下不可判定。

但是上述机构造需要同时运行无数个图灵机,是不可接受的。不过很容易将上述改造为可接受的构造:
构造H(Lk,Pi),H包含一个循环,在第j次循环中,H先枚举出图灵机Hj的仿真程序,然后将已经枚举出的图灵机H0-Hj的仿真程序分别单步执行一步。显然,H的任何一次循环都必然在有限步骤内结束,只不过越往后循环周期越长。这样,只要Pi在Lk内可判定,那么必然存在某个Hj在运行m个步骤后停机给出判定结果,那么H(Lk,Pi)就必然在第j+m个循环之内停机。反之,如果Pi在Lk内不可判定,那么H永远也不停机。

于是,H就是符合前述要求的图灵机。

现在,我们要利用H(Lk,Pi,Dk)来构造一个永不停机的图灵机X,X不接受任何输入,但X对于任何一个形式系统Lk中任何一个可判定问题Pi,都可以在有限时间内输出其判定结果(连同Lk和Pi的编号一起输出),而对于任何一个不可判定的问题,X都永远不给出对该问题的任何输出。

类似于构造H的过程,我们先考虑一个不可行的构造,然后改造为可行的构造:
二元组(Lk,Pi)显然是一个递归可枚举集,因此可以用自然数n进行编号:n=f(Lk,Pi),(Lk,Pi)=g(n),f和g互为反函数。
构造无穷多图灵机Xn,其定义为:如果H(g(n))停机输出判定结果d,Xn就输出(n,d)。显然,只要Pi在Lk中可判定,Xn就必然在有限步骤内停机并输出(n,d),反之Xn永不停机。
如果将所有的Xn同时启动,那么任何Lk中的任何可判定问题Pi,都必然在有限步骤内被某个Xn输出,输出内容为(n,d),其中n=f(Lk,Pi)。

上述构造当然也是不可接受的,我们仿照改造H的方法改造X
构造图灵机X,X包含一个循环,在第n次循环中,X先枚举出图灵机Xn的仿真程序,然后将已经枚举出的图灵机X0-Xn的仿真程序分别单步执行一步。显然,X的任何一次循环都必然在有限步骤内结束,只不过越往后循环周期越长。这样,对于任何Lk中的任何Pi,只要Pi在Lk中是可判定的且判定结果为d,那么Xn(n=f(Lk,Pi))必然在某个有限步骤s处停机并输(n,d),而Xn的第s步必然在X的第n+s个循环中被执行到,X必然在n+s个循环之内,输出(n,d)。对于任何形式系统中的任何不可判定的问题,X永远都不会输出判定结果。

于是,X就是符合前述要求的图灵机。

现在澄清几件事情:
1.H和X都不会对任何形式系统中的任何不可判定问题给出判定。
2.对于任何Lk中的任何【Pi】,无论【Pi】在Lk中是否可判定,都存在整数i’,使得【Pi’】==【Pi在Lk中可判定】,因此【Pi在Lk中可判定】这个问题迟早会被X枚举出来并尝试对之进行判定。只要【Pi在Lk中可判定】在某个形式系统Lk’中可判定,那么【Pi在Lk中可判定】的判定结果必然会在有限步骤内被X输出。
3.X在枚举Xn的过程中,许多Xn是根本不会停机的,而每次循环中X都必须单步执行所有尚未停机的Xn,因此X的效率会越来越低。但正如我们前面所讨论的,只要一个问题可以判定,X必然会在有限步骤内输出这个问题的判定,X的能力不会随着效率越来越低而变弱。如果实在觉得这种垃圾越来越多的系统很不舒服,那么还存在这样一个优化:每当某个Xn停机输出了某个问题A的判定结果,就检查A的内容是不是在断言另一个问题B不可判定,如果A有效断言出B不可判定,那么就将正在尝试判定B的图灵机从循环中删除。甚至还可以对B做个标记,在枚举新问题的时候,凡是将问题B作为子问题的问题,都将被直接跳过。不过这些优化其实没什么意义,我们的目的仅仅是讨论图灵机的计算能力,并不关心性能。

——————————————————————————————
现在说一点题外话,数学上明明允许图灵机不可判定的问题存在,也允许超越图灵机的计算模型存在,而我们仅仅对数学家做了一个简单的限制,数学家的计算能力就被限制成不超越图灵机了呢?

这个问题很简单。我们所说的形式系统当然都是有限刻画的。数学家可以谈论某些必须由无限符号才能刻画的数学系统的存在性,甚至谈论这些系统的某些能力和限制,但完全无法使用这些系统进行推理。我们之所以可以谈论这些系统的某些能力和限制,是因为精确分析这些东西仅仅需要有限符号。于是,图灵机也一样可以给出关于这些系统的某些有限符号就可以刻画的属性的判定结果。

事实上,即便是我们熟悉的实数集,其中属性能够被有限符号所精确刻画的实数(也包括π、e、γ等)也只是实数集的一个可数子集。

除非数学家可以分辨出连续统那么多不同的符号甚至更多,以至于整个实数轴的每一个实数对于数学家来说一目了然,那么数学家也就具备了Hyper Computing的能力,我在文章开头对数学家所做的假设也就不再成立了。但这种情况下,数学家所能够提出的机械计算模型肯定要比图灵机更强。这种数学家的本事简直赶上上帝了,我们有能力回答的一切数学问题,对于这种超级数学家来说都可以一眼看出答案。

镜子中的东西左右颠倒这种事情居然也会让那么多人迷惑

镜子放在哪个方向上,像就在哪个方向颠倒。放在上或下就上下颠倒,放在左或右就左右颠倒,放在前或后就前后颠倒。不同意这一点的回家自己动脑子去。

空间一个物体沿任何一个方向经过一次颠倒而得到的所有颠倒的像,都可以通过旋转而相互叠合。所以所谓的左右颠倒、前后颠倒、上下颠倒这几个说法根本就没有区别,只不过后二者听起来比较别扭而已。因为人体左右对称程度最高,而上下和前后就不是很对称,所以左右颠倒最容易引起我们自己的困惑,如果不做一点破坏左右对称性的动作,就不容易看出自己的左右被颠倒了。镜子放在正前方,引起的颠倒本来是前后颠倒,但“前后颠倒”跟“向后转”然后再“左右颠倒”完全是一个效果,所以说左右颠倒也没错。所以根本就没必要说“左右颠倒”,简单的说“颠倒”就够了,因为所有的不同方向的颠倒之间只差个旋转。

对称性当然是个大问题,但这个镜子问题却是个蠢问题。不要因为在科普文章里面看到了对称性,就以为这种镜子对称问题在科学中也是个大问题,它只不过是有关对称性的一个小小的引导问题罢了。

在群论的语言中,三维空间中反射和旋转都是O(3)群的元素,单纯的旋转构成了O(3)的子群SO(3)。O(3)中不属于SO(3)的元素,都是带有反射的转动,任何两个带有反射的转动x0和x1(不属于SO(3)),都可以通过某个纯转动r(属于SO(3))相互联系:x1 = r·x0。也就是说,随便在哪个方向上的反射,都可以通过另外一个方向上的反射跟随一个旋转而得到。

关于贝叶斯主义

扣薪 12:25:58
晃晃对主观贝叶斯主义咋看的?
晃晃 12:31:35
贝叶斯主义是对贝叶斯定理的滥用
晃晃 12:31:50
根本就是用错了
晃晃 12:32:34
贝叶斯定理需要对随机事件的分布猜测一个模型,然后确定模型参数
晃晃 12:33:25
而贝叶斯主义要么没有说如何得到这个模型,要么武断地采用某种特殊模型
晃晃 12:34:52
例如判断太阳明天是否会继续从东方升起,贝叶斯主义的模型就是假定太阳每天升起的概率都相同,然后通过历史积累的数据来计算这个概率有多高
扣薪 12:36:15

晃晃 12:36:46
这不可能是正确的。如果我现在正在做一个工作,每天都经过一个门,但一年以后我会做其他工作不再经过这个门,事先已经计划好了。那么对我来说这一年之内我经过这个门的概率都是高的,而一旦过了一年,我经过这个门的概率就变得很低。
晃晃 12:37:02
如果你假定我每天经过这个门的概率是相同的,那么自然会得到错误的结果
aha 12:37:28

晃晃 12:37:31
你不知道我经过这个门的概率随着时间变化的事实,只是粗暴地假定我按照固定的概率经过这个门
晃晃 12:38:12
贝叶斯主义没有告诉我们如何猜测这个模型
扣薪 12:39:45
nice
晃晃 12:40:50
贝叶斯主义的问题还多着呢
晃晃 12:41:02
什么叫做事件,并没有清楚的定义。
扣薪 12:41:08

晃晃 12:41:30
例如太阳每天从东方升起,是每天算一个事件,还是每小时太阳都按照预测在既定的位置都算一个事件?
晃晃 12:41:45
要是每秒钟都算一个事件,那么事件的数量非常多
扣薪 12:41:41
但貌似这玩艺在医学里有点应用
晃晃 12:42:03
使用贝叶斯定理没有什么错误
扣薪 12:42:21

晃晃 12:42:23
因为只要你对概率分布有合理的知识就可以
晃晃 12:43:07
对于我们已经熟知的东西,只是某些参数不知道的情况下,我们自然可以用贝叶斯定理来确定这些参数
晃晃 12:43:34
但是对于我们完全不了解的问题,就不能用
晃晃 12:44:06
例如有些人用贝叶斯主义计算上帝存在的可能性等等,这些都是混账逻辑
扣薪 12:44:48
(哈哈)
扣薪 12:45:29
他们算出来是接近0吗?
晃晃 12:46:52
不同的假定和对事件的规定计算出来的截然不同
晃晃 12:47:14
范围胡乱地分布在(0,1)之间
晃晃 12:47:28
没有任何参考价值
扣薪 12:47:46
(哈哈)

图灵机的能力

目前最流行的符号推导软件具有一些基本的公式推导和逻辑推导的能力,但是这些软件还远远谈不上智能。例如以前我使用Mathematica和Maple的时候,许多结果需要用无穷级数来表达的积分之类的东西是无法自动被这些软件推导出来的。

但事实上我们人类所能够写出的无穷项级数才能精确表示的数学表达式,必然可以用有限个符号所刻画。有时候我们使用“…”来表示无穷级数的项,事实上这是因为我们能够在前面几项中看出规律的时候才使用这种缩写,而这种规律自然是有限符号可以刻画的。或者我们看不出其中的规律,只是求出了前面几项,那么我们所得到的结果自然也就不是完整的,仅仅是只需前面几个有限项就能够描述的非精确描述,这种情况下我们所得到的不完整的计算结果仍然是有限符号可以表达的。

这样,只要引入适当的推导规则,那么许多无穷级数解也可能可以被符号推导软件所推导出来。当然,对于现有的符号计算软件,引入适当的推导规则这种事情还要人来做,软件在闲着没事的时候自己不会去尝试发现这些原来所不具备的推导规则。

不过即便软件在闲着的时候会主动做一些发现新规则的探索游戏,仍然受到一个限制:由于计算机本身的可靠性,这些软件基本上是不会出随机错的,其能力会直接受歌德尔不完备性定理的限制。但图灵早在歌德尔不完备性定理刚刚提出不久就曾经澄清过,歌德尔不完备性定理所限制的是那种仅仅能输出正确结果的机器,而不能限制可能输出错误结果的机器(Penrose在这个问题上确凿无疑滴错乐)。因此,一台挂接了真随机数发生器的以一定概率出错的图灵机(例如读写会以一定的概率把1当成0或者把0当成1,状态迁移会以一定的概率迁入错误的状态,状态迁移表会以一定的概率发生不确定的改变),就不再受歌德尔定理的限制。而且不但如此,不挂接真随机数发生器,使用图灵机自己生成伪随机数,也可以在随机预言模型下(Random Oracle)以任意高的精度模拟带有真随机数发生器的图灵机,只有对那些在计算过程中刚好会出现某种匹配了伪随机数发生器算法序列的问题上显示出其局限。

曾经有人以为量子计算机的能力超越图灵机,但有人做过研究之后认为量子计算机的能力并不能超越带有真随机数发生器的图灵机。目前已经严格证明所有完全由qubit构成的系统最多等价于图灵机,但对于一般的量子计算系统是否都等价于图灵机尚未给出最后的答案。

超限计算在计算能力上超越图灵机,但是需要能够识别无限数量的符号或者拥有无限个状态,这里的无限甚至可以不是可数的无限。我们可以讨论超限计算的能力极限,因为这只需要有限个符号。但是我们却没有能力直接利用这种模型进行实际的计算。虽然物理量的值往往被当作实数,但由于误差的存在,导致事实上我们能够区分的取值只是有限个。虽然量子态在量子力学中是无限精度的,但测量所得的结果只能是本征值,本征值要么只是离散,要么是连续但有误差的,量子态的精确信息在测量过程中丢失了。因此我们现在不知道任何一种在物理上实现可以被我们利用的超限计算机的方式。

我猜,有限状态识别有限符号的计算机的能力上限就是图灵机,不可能超越图灵机,不知道是否能够对此做出严格的证明。

Wallace-Bolyai-Gerwien定理

http://www.oursci.org/bbs/oursci/newreply.php?postid=124894
(三思-冷饭)

这个定理说,两个面积相同的简单多边形A和B,A一定能切割成有限多块再拼起来成B.

证明很简单:

1)简单多边形都能切开成三角形。

2)而任意三角形都能切开拼成矩形(先沿两边中点切开,再把上面的小三角形沿顶角垂线剖开得到两块和下面的梯形一拼就成矩形了)。

3)两个面积相同的矩形,一个切开可以拼成另一个(这个难点,不具体说了,要斜着切)。

4)于是我们可以把两个多边形都分别先切成三角形,再切成各个矩形,然后统一矩形的宽度,于是拼成一个长矩形,因为原先的两个多边形面积一样,这样的两个长多边形必定相同,于是得证。

λ calculus

definition:
–λ formal-parameter. function-body
define an anonymous function

–λ formal-parameter. function-body actual-parameter
replace all the formal-parameter in the function body with the actual-parameters.

some time it is difficult to separate the function body and the actual-parameter, use (): (λ formal-parameter. function-body) (actual-parameter)

eg:
–(λf.f 3)(λx.x + 2)
–where (λf.f 3) means an anonymous function λ(f){f 3}
–so (λf.f 3)(λx.x + 2) means {(λx.x + 2) 3}
–then {(λx.x + 2) 3} means (3 + 2)

–[λf g.(f (g 3))](λx.x + 2)
–where [λf g.(f (g 3))] means an anonymous function λ(f,g){f[g(3)]}
–so [λf g.(f (g 3))](λx.x + 2) means λg.{(λx.x + 2) (g 3)}
–then λg.{(λx.x + 2) (g 3)} means λg.(g(3) + 2)

(λx.x x)(λx.x x) means: use the later (λx.x x) to substitute the (x x) in the former (λx.x x), you get (λx.x x) (λx.x x) again.

(λx.x x x)(λx.x x x) means: use the later (λx.x x x) to substitute the (x x x) in the former (λx.x x x), you get (λx.x x x)(λx.x x x)(λx.x x x), next time you will get (λx.x x x)(λx.x x x)(λx.x x x)(λx.x x x)(λx.x x x)(λx.x x x)…

note: (λx y.x y) (λy.F y) means (λy.(λy.F y)y) <==> (λy.(λz.F z)y) <==> (λy.F y). The scope of formal parameter is local.

Fixed point combinator:

A fixed point combinator (or fixed-point operator) is a higher-order function which computes a fixed point of other functions.

e.g. Suppose “fix” is a fixed point combinator which fix(g) is a fixed point of function g, thus g(fix(g)) = fix(g).

One well-known (and perhaps the simplest) fixed point combinator in the untyped lambda calculus is called the Y combinator. It was discovered by Haskell B. Curry, and is defined as:

Y = λf.(λx.f(x x))(λx.f(x x))

Note that the Y combinator is intended for the call-by-name evaluation strategy, since (Y g) diverges (for any g) in call-by-value settings.

Obviously: Y g = (λx.g(x x))(λx.g(x x)) = g((λx.g(x x)(λx.g(x x)) = g(Y g)
Thus Y g = g(Y g) = g(g(Y g)) = g(g(g(Y g))) …

Factorial function n!, we would simply call g(Y g) n
Where g := λf n. (1, if n = 0; and n·f(n-1), if n > 0).
So g(Y g) = λn. (1, if n = 0; and n·((Y g)(n-1)), if n > 0)
and g(Y g)n = (1, if n = 0; and n·((Y g)(n-1)), if n > 0)
for n = 5:
g(Y g)5 = 5·((Y g)(5-1)) = 5·((Y g)4) = 5·(g(Y g)4) = 5·4·((Y g)3) = 5·4·(g(Y g)3)= … = 5·4·3·2·1

Every recursively defined function can be seen as a fixed point of some other suitable function, and therefore, using Y, every recursively defined function can be expressed as a lambda expression.

A quick sort λ expression:
suppose we have sizeof and pl and pg function
sizeof(array) returns the size of the array.
pl(array) and pg(array) makes a complete partition of the array, where each element in pl(array) is less than each element in pg(array).

q := λs a. a, if sizeof(a)<=1; and s(pl(a)) s(pg(a)), if sizeof(a)>1

q(Y q)
= λa.a, if sizeof(a)<=1; and (Y q)(pl(a)) (Y q)(pg(a))
= λa.a, if sizeof(a)<=1; and (q(Y q))(pl(a)) (q(Y q))(pg(a))

q(Y q)a
= a, if sizeof(a)<=1; and (q(Y q))(pl(a)) (q(Y q))(pg(a))

q(Y q)a is the λ expression of the quick sort function.

Because that Y can calculate the fixed point of any function g, so any recursive function can be represented as per replacing the recursion point with g(Y g):

h(x) := (F(h))(x)
F is some high order function, F(fun) returns a function composed with fun, here we use it to represent the recursive form of function h. This is not a λ expression, because there is an explicit recursion.

let g := λH x.(F(H))(x) then
g(Y g) = λx.(F(Y g))(x) = λx.(F(g(Y g)))(x) ..now this is a valid λ expression.

so
h := g(Y g)
= (λH x.(F(H))(x))(Y (λH x.(F(H))(x)))
= (λH x.(F(H))(x))((λf.(λx.f(x x))(λx.f(x x)))(λH x.(F(H))(x)))
is the λ expression definition for function h

ref:
http://en.wikipedia.org/wiki/Fixed_point_combinator
http://en.wikipedia.org/wiki/Lambda_calculus