Algorithmic Randomness and Complexity

《Algorithmic Randomness and Complexity》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、ThisispageiPrinter:OpaquethisAlgorithmicRandomnessandComplexityRodDowneySchoolofMathematicalandComputingSciencesVictoriaUniversityPOBox600WellingtonNewZealandDenisR.HirschfeldtDepartmentofMathematicsUniversityofChicagoChicagoIL60637U.S.A.July28,2007Thisispag

2、eiiPrinter:OpaquethisContents1Prefacex2Acknowledgementsxiii3IntroductionxvIBackground14Preliminaries24.1NotationandConventions.................24.2BasicsfromMeasureTheory................35ComputabilityTheory65.1Computablefunctionsandthehaltingproblem.....65.

3、2ComputableenumerabilityandRice’sTheorem.....105.3TheRecursionTheorem..................115.4Reductions..........................125.4.1OraclemachinesandTuringreducibility.....135.4.2Strongreducibilities.................155.5Thearithmetichierarchy............

4、......175.6TheLimitLemmaandPost’sTheorem..........185.7Anoteonreductions....................205.8Thefiniteextensionmethod................22Contentsiii5.9Post’sProblemandthefiniteinjurymethod.......255.10Finiteinjuryargumentsofunboundedtype........305.10.1Sacks

5、’SplittingTheorem..............305.10.2ThePseudo-JumpTheorem............325.11Theinfiniteinjurymethod.................345.11.1Prioritytreesandguessing.............345.11.2Theminimalpairmethod.............375.11.3Highcomputablyenumerabledegrees.......445.11.4T

6、heThicknessLemma...............465.12TheDensityTheorem....................495.13JumpTheorems.......................545.14Hyperimmune-freedegrees.................575.15Minimaldegrees.......................605.16Π0andΣ0classes......................62115.16.1Ba

7、sics........................625.16.2Π0andΣ0classes..................63nn5.16.3BasisTheorems...................645.16.4GeneralizingtheLowBasisTheorem.......675.17StrongreducibilitiesandPost’sProgram.........685.18PAdegrees..........................705.19Fixed

8、-pointfreeanddiagonallynoncomputablefunctions725.20DirectcodingintoDNCdegrees..............785.21Arraynoncomputabilityandtraceability.........796KolmogorovComplexityofFiniteStrings866.1PlainKolm