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