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

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),接着再看更方便。

相关小说

说谎后续(长篇) 连载中
说谎后续(长篇)
樊洛迪
重新开始是奖励还是惩罚?是真是假?你的谎言能否换来一次真谛?你的回答是?
1.1万字9个月前
超变战陀之你是我的唯一 连载中
超变战陀之你是我的唯一
蜜桃樱桃酱
主cp:星寒,星空,星澜
0.3万字9个月前
蔷薇少女水银灯之爱的冒险 连载中
蔷薇少女水银灯之爱的冒险
半岛咖啡馆
12.8万字9个月前
我家娘子太妖孽 连载中
我家娘子太妖孽
红捻子
她不过是旧疾发作掉落凡间,躺在树上喝酒,竟然看到一群人欺负几个人,于心不忍,出手相救,万万没想到被人给缠上。
29.1万字9个月前
翔空是…… 连载中
翔空是……
梦零莹
这人很懒,啥都没写。
0.2万字9个月前
清穿:在玛丽苏世界里开挂 连载中
清穿:在玛丽苏世界里开挂
墨青栀
第一个世界:【架空+清穿+双洁】什么!爱新觉罗.福明!这是谁?康熙的父亲难道不是爱新觉罗.福临吗?就是那个24岁病逝,谥号为顺治的那个。哦,......
1.9万字9个月前