j.c.owings%a3%badiagonalization%20and%20the%20recursion%20theorem

《j.c.owings%a3%badiagonalization%20and%20the%20recursion%20theorem》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、95NotreDameJournalofFormalLogicVolumeXIV,Number1,January1973NDJFAMDIAGONALIZATIONANDTHERECURSIONTHEOREMJAMESC.OWINGS,JR.In1938Kleeneshowedthatif/isarecursivefunctionthen,forsomenumberc,φc^

2、mshavebeenfoundwithsimilarproofs.Allofthesetheoremstendtostrainone'sintuition;infact,manypeoplefindthemalmostparadoxical.Themostpopularproofsofthesetheoremsonlyservetoaggravatethesituationbecausetheyarecompletelyunmotivated,seemtodependuponalowcombinatorialtrick,andaresobarbar

3、icallyshortastobenearlyincapableofrationalanalysis.Itisourintention,one,toputKleene'sproofonclassicallyintuitivegroundsbyexplaininghowitcanbeviewedasanaturalmodificationofanordinarydiagonalargumentand,two,topresentaformulationofKleene'stheoremsufficientlyabstracttoyieldallknow

4、nsimilartheoremsascorollaries.Inatypicaldiagonalargumentonehasaclassofsequences(withtermsfromasetS),whichhearrangesastherowsofasquarematrix,andamappingaofSintoS.ThismappinginducesanoperationenontheclassofarbitrarysequencesofelementsofSinthenaturalway—if(s(i):iel)issuchasequenc

5、ethena((s(i):iel))=(a(s(i)):iel).Onethenappliesαtothesequenceofdiagonalelementsofthematrixandshowsthattheresult-ingsequenceisnotarowofthematrix,thusdiagonalizinghimselfoutoftheclassofsequenceshebeganwith.AgoodexampleisthematrixwhoserowsareallinfiniteperiodicsequencesofO'sandΓs

6、(binaryexpansionsofrationale)withthemappinga(0)=1,a(l)=0.Usually,asintheexamplejustgiven,therowsofthematrixareclosedundertheoperationa.Hence,ifthediagonalizationsucceeds,itisusuallytruethatthediagonalsequenceitselfisnotoneoftherows.Butwhatifthediagonalizationfails,thatis,whati

7、fthediagonalsequenceisoneoftherows?Thentheimageofthediagonalsequenceunderαwillalsobeoneoftherows,whichmeanssomememberofthediagonalsequencemustbeleftunchangedundertheactionofa.Inotherwords,αhasafixedpoint!TounderstandKleene'stheoremintheseterms,firstassume/isa•Partiallysupporte

8、dbyNSFgrantGP-6897.ReceivedJuly20,1970,RevisedApril1,197296JA