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

元数学:复杂度、随机性与不完备(二) (4-1)

Chaitin (1987):

Exponential Diophantine Equation #1

Program(n,k) calculates the kth approximation to Ω,in the manner explained in a previous section.Then Program(n,k) looks at the nth bit of this approximate value for Ω.If this bit is a 1,then Program(n,k) immediately halts;otherwise it loops forever.

So Program(n,k) halts if and only if

(the nth bit in the kth approximation to Ω) is a 1.

As k gets larger and larger,the nth bit of the kth approximation to Ω will eventually settle down to the correct value. Therefore for all

sufficiently large k:

Program(n,k) will halt if the nth bit of Ω is a 1.

and Program(n,k) will fail to halt if the nth bit of Ω is a 0.

Using all the work on Hilbert’s 10th problem that we explained in Chapter Two,we immediately get an exponential diophantine

equation

L(n,k,x,y,z,...) = R(n,k,x,y,z,...)

that has exactly one positive-integer solution if Program(n,k)eventually halts,

and that has no positive-integer solution if Program(n,k) never halts.

Therefore,fixing n and considering k to be an unknown,this exact same equation

L(n,k,x,y,z,...) = R(n,k,x,y,z,...)

has infinitely many solutions if the nth bit of Ω is a 1,

and it has only finitely many solutions if the nth bit of Ω is a 0.

Ord,Kieu (2003):

Exponential Diophantine Equation #2

Program(n,k) halts if and only if k>0 and

2"×(jth approximation to Ω) > k

for some j=1,2,3,...

So Program(n,k) halts if and only if 2"×Ω > k > 0.

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

相关小说

尘时愿 连载中
尘时愿
作者一肖
敌国皇子与丞相之女从猜疑、互相试探到互相扶持,完成共同心愿的故事
16.5万字9个月前
虣兽世界 连载中
虣兽世界
蓝桉的小鲨鱼
3.6万字9个月前
异能:云淡风轻 连载中
异能:云淡风轻
殊宠
【黑历史勿入】【已完结】一场惊世骇俗的身份颠倒,她-实验室王牌总研取代了她-真正的慕家大小姐。从此,博士变成了大小姐。大小姐变成了总研。没人......
14.9万字9个月前
绝色炼丹师:失忆后我成了万人迷 连载中
绝色炼丹师:失忆后我成了万人迷
王宋胜利
三百年前,有即将飞升的大能为大陆留下最后一个需要,三百年后将有一个天命之人出现在天圣学院,得此人助力者必可得天下。三百年后,各国势力都在暗中......
27.4万字9个月前
师父为夫:萌徒养成手册 连载中
师父为夫:萌徒养成手册
魂归暮里
【已签约】南笙璃作为仙狐族唯一公主,被人陷害降生凡间南渊皇族本应早夭的公主身上,天生魂魄残缺,却被绝美国师所救并收其为徒。国师将她一手带大,......
7.7万字9个月前
希望战刃 连载中
希望战刃
晓馨SV
鬼人泛滥,大地之上起纷争。顾小雨亲眼目送姐姐与妹妹的惨死,逃生中不知爱人是死是活,但她坚信她之爱人会在某一天,出现在眼前。前提是,她要好好活......
2.5万字9个月前