数学联邦政治世界观
超小超大

SEP:可计算性与复杂性(二) (5-1)

2.4 The Unsolvability of the Halting Problem

图灵问到,对于所有自然数集来说是否其都是可判定的。通过下面的计数论证,我们非常容易地就能知道答案是否定的。N有不可数数量的子集,但由于我们只有可数数量的图灵机,所以也只有可数数量的集合是可判定的。那么最后就是,多数集合都是不可判定的。

图灵实际上构造了一个不可判定集。如我们将看到的那样,他是通过运用对角线法(diagonal argument)来做到的。对角线法可以追溯到康托尔用其去表明实数是不可数的。哥德尔在他对不完备性定理的证明中,也用了一个相似的对角线法,他在数论中构造了这样一个句子J,这个句子的意思是,它本身不可证。

图灵如下地构造了一个对角线式停机集K:

K={n│Mₙ(n)↓}.

这是指K由那些,输入它们自己的程序后最终会停机的图灵机所组成。

不难看到,K是递归可枚举的。为了构造矛盾,假设,K也是共递归可枚举的,并让d为接受K的元素的一台图灵机的数。这样,对于任何n,n ∉ K ⇔ Md(n)↓

但考虑一下,当我们在上面用d代替n时会发生些什么:

d ∉ K ⇔ Md(n)↓

但K的定义告诉我们,

d ∈ K ⇔ Md(d)↓.

这样,我们就有了,

d ∈ K ⇔ d ∉ K

而这是一个矛盾,因此,我们对K是共递归可枚举的假设是错误的。也因此,K将不是递归的。这可以推出,对于一个给定的图灵机及其输入,并判定其最终是否能够停机的问题来说,这不是一个可计算问题,即,停机问题是不可解的。(译注:最先的定义告诉我们d属于K等价于Md输入d时停机,但因为,K是递归可枚举且共递归可枚举的,所以对于任何数n都可以使M停机而不管是其是否属于K,而当我们将d代到其不属于K的n的情况下时,其当然也可以停机,并等价推出d ∈ K,这样就出现了矛盾)

1. Primitive Recursive Functions

我们接下来定义*原始递归函数(primitive recursive functions)*的类(class)。这是一个非常有有意思的函数类,其由Skolem (1923)给出,并被哥德尔运用到了他对不完备性定理的证明中。我们关注于从Nʳ到N的函数f,对于r=0,1,2,. . .,我们称r为函数f的元数,即其中变元的数目。哥德尔从三个非常简单的函数开始,初始函数,以及两个自然闭包运算,合成(composition)与原始递归,它们中都每一个都使用某个已经被定义好的函数,然后去定义一个新函数。下面我们将细节性地解释一下他的定义。这节将比较技术化,你跳过了也没啥关系。关键思想是,原始递归函数由一个非常大且强有力的可计算函数类组成,并且所有它们都以非常简单的方式被生成出来。

我们从三个初始的原始递归函数开始:

• ζ为,元数0的零函数(zero function),ζ()=0;

• η为,元数1的恒等函数(identity function),η(n)=n;以及

• σ为,元数1的后继函数(successor function),σ(n)=n+1。

然后考虑下面两个运算:

• Composition:如果f是一个元数α的原始递归函数,以及g₁,. . .,gα为元数r₁,. . .,rα的原始递归函数, 并且k ∈ N,那么下面是一个元数k的原始递归函数:

h(x₁,. . .,xₖ)=f(g₁(ω₁),. . .,gα(ωα))

数学联邦政治世界观提示您:看后求收藏(同人小说网http://tongren.me),接着再看更方便。

相关小说

S级Omega所托非人? 连载中
S级Omega所托非人?
是废话不是费话
作者也不知道要写什么简介的文
9.0万字8个月前
快穿之反派boss的白月光 连载中
快穿之反派boss的白月光
云中月皎皎
第一个世界(完):把温柔哥哥撩到手了第二个世界(完):那个将军在替我守墓第三个世界(完):在末世我抱紧了大腿第四个世界(完):我是被偷换的真......
28.9万字8个月前
长鲸 连载中
长鲸
鄢粟
“你在窥探未来,迷雾中逆行”“本该如此,不是吗?”“你知道,我们会是你的后盾”“不,你们不是”............“自知迷雾重重,重蹈覆......
2.9万字8个月前
深渊的曙光 连载中
深渊的曙光
冰水寒心
情字一字无解,但求良人共度生。你是我生命中唯一的光,是身处深渊中的我唯一的曙光——等救赎我的光全都消散了,我也该坠入无尽的深渊深处了。待我进......
12.6万字8个月前
寄君相思 连载中
寄君相思
桦桦饿胖了
“兔子的天敌是什么?”“狐狸?”bingo!答对了!“你一只兔子拽什么拽?老子是狐狸!”“小狐狸,你没听说过,兔子急了会咬人的吗?”尹圆青✘......
7.9万字8个月前
异界之在光邙大陆做大做强 连载中
异界之在光邙大陆做大做强
孤字凌
哈喽,这里是光邙大陆。什么?你想知道凌江月女神的传奇故事?其实,她刚开始也是个啥也不懂的小屁孩!那她是怎么成功的?成功是需要99%的汗水嘛,......
7.5万字8个月前