05590nam 2200685Ia 450 991081345700332120230721033026.01-281-93434-89786611934347981-279-405-0(CKB)1000000000549533(EBL)1193153(SSID)ssj0000292343(PQKBManifestationID)11237016(PQKBTitleCode)TC0000292343(PQKBWorkID)10269176(PQKB)10355065(MiAaPQ)EBC1193153(WSP)00001767 (Au-PeEL)EBL1193153(CaPaEBR)ebr10698842(CaONFJC)MIL193434(OCoLC)820944486(EXLCZ)99100000000054953320080319d2008 uy 0engurcn|||||||||txtccrComputational prospects of infinity[electronic resource] Part ITutorials /editors, Chitat Chong ... [et al.]Singapore ;Hackensack, NJ World Scientificc20081 online resource (264 p.)Lecture notes series / Institute for Mathematical Sciences, National University of Singapore ;v. 14Description based upon print version of record.981-279-653-3 Includes bibliographical references.CONTENTS; Foreword; Preface; Recursion Theory Tutorials; Five Lectures on Algorithmic Randomness Rod Downey; 1. Introduction; 2. Lecture 1: Kolmogorov complexity basics; 2.1. Plain complexity; 2.2. Symmetry of Information; 2.3. Pre.x-free complexity; 2.4. The Coding Theorem; 2.5. Pre.x-free symmetry of information; 2.6. Pre.x-free randomness; 2.7. The overgraph functions; 3. Lecture 2: Randomness for reals; 3.1. Martin-L ̈of randomness; 3.2. Schnorr's Theorem and the computational paradigm; 3.3. Martingales and the prediction paradigm; 3.4. Super martingales and continuous semimeasures3.5. Schnorr and computable randomness 4. Lecture 3: Randomness in general; 4.1. The de Leeuw, Moore, Shannon, Shapiro Theorem, and Sacks' Theorem; 4.2. Coding into randoms; 4.3. Kucera Coding; 4.4. n-randomness; 4.5. Notes on 2-randoms; 4.6. Kucera strikes again; 4.7. van Lambalgen's Theorem; 4.8. Effective 0-1 Laws; 4.9. Omega operators; 5. Lecture 4: Calibrating randomness; 5.1. Measures of relative randomness and the Kucera-Slaman Theorem; 5.2. The Density Theorem; 5.3. Other measures of relative randomness; 5.4. <C and <K.; 5.5. Outside of the randoms; 5.6.5.7. Hausdor. Dimension 6. Lecture 5: Measure-theoretical injury arguments; 6.1. Risking measure; 6.2. 2-random degrees are hyperimmune; 6.3. Almost every degree is CEA; References; Global Properties of the Turing Degrees and the Turing Jump Theodore A. Slaman; 1. Introduction; 1.1. Style; 2. The coding lemma and the rst order theory of the Turing degrees; 2.1. The coding lemma; 3. Properties of automorphisms of D; 3.1. Results of Nerode and Shore; 4. Slaman and Woodin analysis of Aut(D); 4.1. Persistent automorphisms; 4.2. Persistently extending persistent automorphisms4.3. Persistence and reection 4.4. Generic persistence; 4.5. Denability of automorphisms of D; 4.6. Invariance of the double jump; 5. Denability in D; 5.1. Bi-interpretability; 6. The Turing jump; 6.1. Recursive enumerability; References; Set Theory Tutorials; Derived Models Associated to Mice John R. Steel; 1. Introduction; 2. Some background and preliminaries; 2.1. Homogeneously Suslin sets; 2.2. Hom1 iteration strategies; 2.3. The derived model; 2.4. Iterations to make RV = R; 2.5. Premice over a set; 3. Iteration independence for derived models of mice4. Mouse operators and jump operators 5. The mouse set conjecture in D(M; ); 6. The Solovay sequence in D(M; ); 7. The -transform; 8. A long Solovay sequence; 9. The mouse set conjectures: Framework of the induction; 10. The background universe N; 11. The L[E]-model Nx; 12. Two hybrid mouse operators at 0; 13. New mice modulo (y); 15. The consistency strength of AD+ + 0 <; 16. Global MSC implies the local MSC; 17. MSC implies capturing via R-mice; References; Tutorial Outline: Suitable Extender Sequences W. Hugh Woodin; 1. Introduction; 2. Generalized iteration trees2.1. Long extendersThis volume presents the written versions of the tutorial lectures given at the Workshop on Computational Prospects of Infinity, held from 18 June to 15 August 2005 at the Institute for Mathematical Sciences, National University of Singapore. It consists of articles by four of the leading experts in recursion theory (computability theory) and set theory. The survey paper of Rod Downey provides a comprehensive introduction to algorithmic randomness, one of the most active areas of current research in recursion theory. Theodore A Slaman's article is the first printed account of the ground-breakingLecture notes series (National University of Singapore. Institute for Mathematical Sciences) ;v. 14.Recursion theoryCongressesSet theoryCongressesInfiniteCongressesRecursion theorySet theoryInfinite511.322Chong C.-T(Chi-Tat),1949-441174MiAaPQMiAaPQMiAaPQBOOK9910813457003321Computational prospects of infinity4012909UNINA