Algorithms for Constructing Computably Enumerable Sets / / by Kenneth J. Supowit |
Autore | Supowit Kenneth J. |
Edizione | [1st ed. 2023.] |
Pubbl/distr/stampa | Cham : , : Springer International Publishing : , : Imprint : Birkhäuser, , 2023 |
Descrizione fisica | 1 online resource (191 pages) |
Disciplina | 004.0151 |
Collana | Computer Science Foundations and Applied Logic |
Soggetto topico |
Computer science
Computable functions Recursion theory Set theory Computer science—Mathematics Theory of Computation Computability and Recursion Theory Set Theory Theory and Algorithms for Application Domains Mathematics of Computing |
ISBN |
9783031269042
9783031269035 |
Formato | Materiale a stampa |
Livello bibliografico | Monografia |
Lingua di pubblicazione | eng |
Nota di contenuto | 1 Index of notation and terms -- 2 Set theory, requirements, witnesses -- 3 What’s new in this chapter? -- 4 Priorities (a splitting theorem) -- 5 Reductions, comparability (Kleene-Post Theorem) -- 6 Finite injury (Friedberg-Muchnik Theorem) -- 7 The Permanence Lemma -- 8 Permitting (Friedberg-Muchnik below C Theorem) -- 9 Length of agreement (Sacks Splitting Theorem) -- 10 Introduction to infinite injury -- 11 A tree of guesses (Weak Thickness Lemma) -- 12 An infinitely branching tree (Thickness Lemma) -- 13 True stages (another proof of the Thickness Lemma) -- 14 Joint custody (Minimal Pair Theorem) -- 15 Witness lists (Density Theorem) -- 16 The theme of this book: delaying tactics -- Appendix A: a pairing function -- Bibliograph -- Solutions to selected exercises. |
Record Nr. | UNINA-9910726280003321 |
Supowit Kenneth J. | ||
Cham : , : Springer International Publishing : , : Imprint : Birkhäuser, , 2023 | ||
Materiale a stampa | ||
Lo trovi qui: Univ. Federico II | ||
|
Calvin C. Elgot selected papers / edited by Stephen L. Bloom ; with a foreword by Dana S. Scott and "A glimpse back" by Samuel Eilenberg |
Autore | Elgot, Calvin C. |
Pubbl/distr/stampa | New York : Springer-Verlag, c1982 |
Descrizione fisica | xxiv, [460] p. : ill. ; 24 cm. |
Disciplina | 510 |
Altri autori (Persone) | Bloom, Stephen L. |
Soggetto topico |
Elgot, Calvin C.-selected papers
Machine theory Mathematics Recursion theory |
ISBN | 0387906983 |
Classificazione | QA3.E5825 |
Formato | Materiale a stampa |
Livello bibliografico | Monografia |
Lingua di pubblicazione | eng |
Record Nr. | UNISALENTO-991000730739707536 |
Elgot, Calvin C. | ||
New York : Springer-Verlag, c1982 | ||
Materiale a stampa | ||
Lo trovi qui: Univ. del Salento | ||
|
Classical recursion theory [e-book] / Piergiorgio Odifreddi |
Autore | Odifreddi, Piergiorgio |
Pubbl/distr/stampa | Amsterdam ; New York : North-Holland : Elsevier, 1989-1999 |
Descrizione fisica | 949 p. : ill. ; 23 cm |
Disciplina | 511.3 |
Collana | Studies in logic and the foundations of mathematics, 0049-237X ; 143 |
Soggetto topico | Recursion theory |
ISBN |
9780444502056
044450205X |
Classificazione | AMS 03D |
Formato | Risorse elettroniche |
Livello bibliografico | Monografia |
Lingua di pubblicazione | eng |
Record Nr. | UNISALENTO-991003272489707536 |
Odifreddi, Piergiorgio | ||
Amsterdam ; New York : North-Holland : Elsevier, 1989-1999 | ||
Risorse elettroniche | ||
Lo trovi qui: Univ. del Salento | ||
|
Classical recursion theory : the theory of functions and sets of natural numbers / Piergiorgio Odifreddi |
Autore | Odifreddi, Piergiorgio |
Pubbl/distr/stampa | Amsterdam : North-Holland, 1989 |
Descrizione fisica | xvii, 668 p. ; 24 cm |
Disciplina | 511.3 |
Collana | Studies in logic and the foundations of mathematics, 0049-237X ; 125 |
Soggetto topico | Recursion theory |
ISBN | 0444872957 |
Classificazione |
AMS 03D
LC QA9.6.O35 |
Formato | Materiale a stampa |
Livello bibliografico | Monografia |
Lingua di pubblicazione | eng |
Record Nr. | UNISALENTO-991000744919707536 |
Odifreddi, Piergiorgio | ||
Amsterdam : North-Holland, 1989 | ||
Materiale a stampa | ||
Lo trovi qui: Univ. del Salento | ||
|
Combinatorial functors / J. N. Crossley, Anil Nerode |
Autore | Crossley, John N. |
Pubbl/distr/stampa | Berlin ; New York : Springer-Verlag, 1974 |
Descrizione fisica | viii, 146 p. ; 24 cm. |
Disciplina | 511.3 |
Altri autori (Persone) | Nerode, Anilauthor |
Collana |
Ergebnisse der Mathematik und ihrer Grenzgebiete. 2. Folge ; 81
Ergebnisse der Mathematik und ihrer Grenzgebiete. 2. Folge, 0071-1136 ; 81 = A series of modern surveys in mathematics, 0071-1136 ; 81 |
Soggetto topico |
Combinatorial analysis
Functor theory Model theory Recursion theory |
ISBN | 3540064281 |
Classificazione |
AMS 03C
AMS 03D |
Formato | Materiale a stampa |
Livello bibliografico | Monografia |
Lingua di pubblicazione | eng |
Record Nr. | UNISALENTO-991000755499707536 |
Crossley, John N. | ||
Berlin ; New York : Springer-Verlag, 1974 | ||
Materiale a stampa | ||
Lo trovi qui: Univ. del Salento | ||
|
Computability : an introduction to recursive function theory / Nigel Cutland |
Autore | Cutland, Nigel |
Pubbl/distr/stampa | Cambridge : Cambridge University Press, 1980 |
Descrizione fisica | x, 251 p. ; 23 cm. |
Disciplina | 519.4 |
Soggetto topico |
Computable functions
Recursion theory |
ISBN | 0521294657 |
Classificazione |
AMS 03D
QA9.59.C87 |
Formato | Materiale a stampa |
Livello bibliografico | Monografia |
Lingua di pubblicazione | en |
Record Nr. | UNISALENTO-991000772779707536 |
Cutland, Nigel | ||
Cambridge : Cambridge University Press, 1980 | ||
Materiale a stampa | ||
Lo trovi qui: Univ. del Salento | ||
|
Computability theory / Rebecca Weber |
Autore | Weber, Rebecca |
Pubbl/distr/stampa | Providence, R. I. : American Mathematical Society, c2012 |
Descrizione fisica | vii, 203 p. : ill. ; 22 cm |
Disciplina | 511.352 |
Collana | Student mathematical library, 1520-9121 ; 62 |
Soggetto topico |
Recursion theory
Computable functions |
ISBN | 9780821873922 |
Classificazione |
AMS 03D
AMS 68Q LC QA9.6.W43 |
Formato | Materiale a stampa |
Livello bibliografico | Monografia |
Lingua di pubblicazione | eng |
Record Nr. | UNISALENTO-991001839319707536 |
Weber, Rebecca | ||
Providence, R. I. : American Mathematical Society, c2012 | ||
Materiale a stampa | ||
Lo trovi qui: Univ. del Salento | ||
|
Computation and proof theory : proc. of the Logic Colloquium held in Aachen, July 18-23, 1983 / eds. G. H. Muller, M. M. Richter |
Autore | Borger, Egon |
Disciplina | 511.3 |
Altri autori (Persone) |
Oberschelp, Walter
Richter, Michael M. Schinzel, Brigitta Thomas, Wolfgang |
Soggetto topico | Recursion theory |
ISBN | 354013901X |
Classificazione |
AMS 03D
AMS 03F AMS 68-XX |
Formato | Materiale a stampa |
Livello bibliografico | Monografia |
Lingua di pubblicazione | eng |
Record Nr. | UNISALENTO-991000773229707536 |
Borger, Egon | ||
Materiale a stampa | ||
Lo trovi qui: Univ. del Salento | ||
|
Computational prospects of infinity [[electronic resource] ] . Part I Tutorials / / editors, Chitat Chong ... [et al.] |
Pubbl/distr/stampa | Singapore ; ; Hackensack, NJ, : World Scientific, c2008 |
Descrizione fisica | 1 online resource (264 p.) |
Disciplina | 511.322 |
Altri autori (Persone) | ChongC.-T <1949-> (Chi-Tat) |
Collana | Lecture notes series / Institute for Mathematical Sciences, National University of Singapore |
Soggetto topico |
Recursion theory
Set theory Infinite |
Soggetto genere / forma | Electronic books. |
ISBN |
1-281-93434-8
9786611934347 981-279-405-0 |
Formato | Materiale a stampa |
Livello bibliografico | Monografia |
Lingua di pubblicazione | eng |
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. 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 |
Record Nr. | UNINA-9910452972103321 |
Singapore ; ; Hackensack, NJ, : World Scientific, c2008 | ||
Materiale a stampa | ||
Lo trovi qui: Univ. Federico II | ||
|
Computational prospects of infinity [[electronic resource] ] . Part I Tutorials / / editors, Chitat Chong ... [et al.] |
Pubbl/distr/stampa | Singapore ; ; Hackensack, NJ, : World Scientific, c2008 |
Descrizione fisica | 1 online resource (264 p.) |
Disciplina | 511.322 |
Altri autori (Persone) | ChongC.-T <1949-> (Chi-Tat) |
Collana | Lecture notes series / Institute for Mathematical Sciences, National University of Singapore |
Soggetto topico |
Recursion theory
Set theory Infinite |
ISBN |
1-281-93434-8
9786611934347 981-279-405-0 |
Formato | Materiale a stampa |
Livello bibliografico | Monografia |
Lingua di pubblicazione | eng |
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. 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 |
Record Nr. | UNINA-9910782357403321 |
Singapore ; ; Hackensack, NJ, : World Scientific, c2008 | ||
Materiale a stampa | ||
Lo trovi qui: Univ. Federico II | ||
|