如果你觉得太孤单，与Ｉ相关的函数有Φ函数。

Φ(0,α)=Ω_α

Φ(0,Φ(0,Φ(0,……)))=Φ(1,0)=Ω_Ω_Ω_……=Ｉ（φ函数的味）

ψ(Φ(1,1))=ψ(Φ(0,Φ(0,Φ(0,……Φ(1,0)))))=ψ(ψ_Ｉ(1))

ψ(Φ(2,0))=ψ(Φ(1,Φ(1,Φ(1,……Φ(1,0)))))=ψ(ψ_Ｉ(Ｉ))

ψ(Φ(2,1))=ψ(ψ_Ｉ(Ｉ2))

ψ(Φ(3,0))=ψ(ψ_Ｉ(Ｉ2))

ψ(Φ(4,0))=ψ(ψ_Ｉ(Ｉ3))

ψ(Φ(1,0,0))=ψ(ψ_Ｉ(Ｉ^Ｉ))

ψ(ψ_Ｉ(Ｉ^Ｉ^ω))=ψ(Φ(1,0,0,0,……))，Ｉ版的SVO。

ψ(ψ_Ｉ(Ｉ^Ｉ^Ｉ))，Ｉ版的LVO。

ψ(ψ_Ｉ(Ｉ^Ｉ^Ｉ^……))=ψ(ψ_Ｉ(ψ_(Ω_Ｉ+1)(0)))=ψ(ψ_(Ω_Ｉ+1)(0))，Ｉ版的BHO。

ψ(ψ_(Ω_Ｉ+1)(Ｉ))=ψ(ψ_(Ω_Ｉ+1)(ψ_Ｉ(ψ_(Ω_Ｉ+1)(……ψ_Ｉ(ψ_(Ω_Ｉ+1)(0))))))，Ｉ被加强了，琢磨一下。

ψ(ψ_(Ω_Ｉ+1)(Ω_Ｉ+1))=ψ(ψ_(Ω_Ｉ+1)(ψ_(Ω_Ｉ+1)ψ_(Ω_Ｉ+1)……(0)))

α→ψ(ψ_(Ω_Ｉ+α))的序数不动点为ψ_Ｉ(2)(0)，不要认为它是ψ(ψ_Ω_Ｉ(Ω_(Ｉ2)))。

ψ(Ｉ(3))

ψ(Ｉ(Ｉ(Ｉ……(Ｉ(Ｉ(Ｉ))))))=Ｉ(1,0)

ψ(Ｉ(1,0,0))多元φ函数：又学我

ψ(Ｉ(1,0,0,0))

ψ(Ｉ(1@4))

再往下走下去又有ψ(Ｉ(1@ψ(Ｉ(1@1))))等等。

如果觉得太麻烦，还有χ函数，里面还有Ｍ（马洛序数），它与Ｉ序列的关系是：

Ｉ(α?@(1+β?),……α?@(1+β?),α?@(1+β?),α?

)=χ(Ｍ^α?β?+……+Ｍ^α?β?+Ｍ^α?β?,α?)

ψ(Ｉ(ω@ω))=ψ(χ(Ｍ^Ｍ^ω))

ψ(Ｉ(ω@ω@ω))=ψ(χ(Ｍ^Ｍ^Ｍ^ω))

就这样一直下去，你也可以自己造一个新的函数，继续下去，就像有限世界一样……

有限的尽头是无限。那么，按理说，一直这样下去也要有个头啊。

没错，这个头就是非递归序数。

非递归序数，字面意思就是指不能用任何运算和递归关系来达到的数。因此，非递归序数就像一个升级的无穷序数。

非递归序数也分多个。第一个非递归序数是ω???（其中，下标1表示第1个，上标cK表示非递归的教堂克林序数），即教堂克林序数。然而它依然是有限序数:(

第二个非递归序数是ω???，它则是所有由ω???通过各种递归运算得出的序数的集合。

运可以增强下标弄出更多的序数。（ω???）

顺便说一下，教堂克林序数可以表示忙碌海狸函数，Σ(n)的增长率为ω???，Σ?(2)=ω???+1，高阶图灵机的增长率Σ?(n)为ω???

————————

只要图灵机选的恰当，f_w1ck可以被f_w+3超越

LetObeKleene’ssystemofordinalnotations.EveryaPOautomaticallyproduces

afundamentalsequenceforthecorrespondingordinal.Therefore,thenotationaPO

automaticallygeneratesthea-thfastgrowingfunctionfainastraightforwardmanner.

Notethatfadependsonthenotationa,butnotontheordinal|a|O.

Putα0asthenotationfortheordinal0,and

αn`1“mintmPO|m?αnand|m|O?|αn|Ou.

Thesequencep|αn|Oqn?ωisclearlyafundamentalsequenceforωCK

1.Then,wedefine

fωCK

1pnq“fαnpnq.

Evenifweusetheabovenaturalfundamentalsequencepαnqn(orpγnqn),weshowthat

itispossiblethatfωCK

1

maybeveryslowgrowing.Thisisduetothebasicobservation

thatthedefinitionofO(hencefωCK

1)heavilydependsonagivennumberingofpartial

computablefunctions.

Proposition1.Thereisanadmissiblenumberingofpartialcomputablefunctionssuch

thatfωCK

1

isdominatedbythepω`3qrdfastgrowingfunctionfω`3.

Proof.LetΦbeacanonicaladmissiblenumberingofpartialcomputablefunctions.One

canassumethatforalmostallethereisdwithe?d?2esuchthatΦdp0q“eand

Φdpn`1q“2Φdpnq.Inotherwords,ifeisacodeofanordinalα,thenΦdpnqisacodeof

α`n;hence35disacodeforα`ω.Forexample,inausualprogramminglanguage,

thereisaconstantc(independentofe)suchthatthelength|d|?log2pdqofsucha

programdisboundedby|e|`c.

WeconstructanewnumberingΨbydefining

Ψ2epnq“

#

2òòn,

ifn?fp3q

ω`3p352e`3q,

Φe,

otherwise.

andΨ2e`1“Φe.ItiseasytocheckthatΨisadmissible.Wenowassumethatthenew

numberingΨisusedtodefineO(hencepαnqn).

Wefirstclaimthatαn-“352e`1foranyn,e.If352e`1RO,theclaimtrivially

holds,soweassume352e`1PO.Then,thefunctionΨ2e`1isincreasingw.r.t.?O;

hence2òòn?OΨ2e`1pnqforanyn.ThisimpliesthatΨ2eisalsoincreasingw.r.t.?O,

whichmeans352ePO.SinceΨ2epnq“Ψ2e`1pnqholdsforalmostalln,wehave

ta:a?O352eu“ta:a?O352e`1u.Thus,352e`1cannotbeequaltotheleastm

suchthatαn′1?mand|αn′1|O?|m|O(orαn′1?Om).

Assumethatαn“2bforsomebandn?0.

Weclaimthatαn′1“b.

First,

|αn′1|O?|αn|O“|b|O`1implies|αn′1|?|b|O.Ifαn′1?bthen|αn′2|O?|αn′1|O?

|b|Oischosenasαn′1,acontradiction.Thus,wecanassumeαn′1?b.Notethat

|αn′1|O?|b|Oisimpossible;otherwisebmustbechosenasαnbyourassumption

αn′1?b.Hence,|αn′1|O“|b|O.Ifαn′1?b,wehave2αn′1?2b;hence2αn′1ischosen

asαn.Asaconsequence,weobtainαn′1“b.

Hence,ifαncodesanordinalλ`pforsomelimitλandfinitep,thenwehavea

sequenceαn′p?Oαn′p`1?O?Oαnwhichcodesλ?λ`1??λ`p.Put

m“n′p.Thenαmisoftheform352e.Ifmissufficientlylarge,asmentioned

above,thereisdwithe?d?2esuchthat352dcodestheordinalλ`ω.Then

1

——————————

352d?352e?expp4q

2peq:“2222e

;hence,thenumber352dcodingλ`ωhashigher

prioritythanthenumberexpp4q

2peqcodingλ`4.Inotherwords,wemusthavep?3.

WenowcalculatefωCK

1pnq.Asobservedabove,foralmostalln,αnisoftheform

expppq

2p352eqforsomep?3.Ifp“0,asαnis?-increasing,weclearlyhaven?352e.

Hence,foranyp?3,wehaven?352e`3.Ifp“0,ourdefinitionofΨ2eensuresthat

fαnpmq“fmpmq“fωpmqforanym?fp3q

ω`3pa`3q,wherea“352e.Ifm?fp2q

ω`3pa`3q,

then

fpmq

ω

′

fp2q

ω`3pa`3q

ˉ

?fω`1

′

fp2q

ω`3pa`3q

ˉ

?fp2q

ω`3pa`3q

andthus,ifp“1,thenfαnpmq“fpmq

a

pmq“fpmq

ω

pmq“fω`1pmqforanysuchm.

Similarly,onecanobservethat,ifp“2,thenfαnpmq“fω`2pmqforanym?fω`3pa`3q,

andifp“3,thenfαnpmq“fω`3pmqforanym?a`3.Inanycase,wehavefαnpnq?

fω`3pnqsincen?a`3asobservedabove.Consequently,fωCK

1pnq“fαnpnq?fω`3pnq

foralmostalln,thatis,fωCK

1

isdominatedbyfω`3.

□

本书由小说网提供。

活动:注册会员赠200点卷,