Computational prospects of infinity [[electronic resource] ] . Part I Tutorials / / editors, Chitat Chong ... [et al.]

• Record Nr.: UNINA9910813457003321
• Pubbl/distr/stampa: Singapore ; ; Hackensack, NJ, : World Scientific, c2008
• ISBN: 1-281-93434-8; 9786611934347; 981-279-405-0
• Descrizione fisica: 1 online resource (264 p.)
• Collana: Lecture notes series / Institute for Mathematical Sciences, National University of Singapore ; ; v. 14
• Altri autori (Persone): ChongC.-T <1949-> (Chi-Tat)
• Disciplina: 511.322
• Soggetti: Recursion theory; Set theory; Infinite
• Lingua di pubblicazione: Inglese
• Formato: Materiale a stampa
• Livello bibliografico: Monografia
• Note generali: Description based upon print version of record.
• Nota di bibliografia: Includes bibliographical references.
• Nota di contenuto: 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 semimeasures; 3.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 automorphisms; 4.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 mice; 4. 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 trees; 2.1. Long extenders
• Sommario/riassunto: This 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-breaking