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

元数学:复杂度、随机性与不完备(二) (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),接着再看更方便。

相关小说

穿越成客栈老板娘 连载中
穿越成客栈老板娘
山河如酒
一觉醒来天塌了,穿越啦?!庆幸的是在这里找到了闺蜜闺蜜告诉我说这里是她写的一本小说。而我是个路人甲她穿成了女配还好我俩觉醒了系统我的系统我躺......
0.8万字9个月前
我在恐怖无限流中加冕 连载中
我在恐怖无限流中加冕
莱利喵_9761905707972209
林淡一朝进入无限流世界,本以为自己很快就会被咔嚓掉。没想到那些鬼怪一见到自己就害怕的逃走。于是她一路斩妖除魔,成为了鬼界巨擘。副本一:诡异渔......
0.4万字8个月前
在无名之书中 连载中
在无名之书中
绿子green
什么?穿书?那既来之则安之好了!女主(非女主)貌美但生得实在愚蠢怎么办?嗯!这妹子好生可爱!!!什么?男的!反派团……好有逼格!闪开我来!雷......
0.2万字8个月前
夫君排排坐,娘子请翻牌 连载中
夫君排排坐,娘子请翻牌
上谛的莞筱
现代重生言情宠文《朕若不死尔等终究是臣》已开启…他----君必熙,身为一国之君,却被她毁了初恋,下半辈子还要被判有“妻”徒刑。他----罗迦......
132.9万字8个月前
社畜只想早点下班 连载中
社畜只想早点下班
懒摇白羽扇
[目前停更][双男主][1V1甜文][忠犬霸道总裁×沙雕女装大佬]作为小说位面维护局的员工,楚酩竟第二次穿进了同一本小说里?新的身份竟是被妹......
8.3万字8个月前
秦风楚芸 连载中
秦风楚芸
山有木兮_744252918
我原是天上观音菩萨紫竹林边缘的一只小绵羊,平凡的微不足道!许是听得观音菩萨讲大乘佛法听得多了,我竟然只用8年的时间修成了人形!我还顺利成了十......
12.5万字8个月前