Info
- Utilizzare la checkbox di selezione a fianco di ciascun documento per attivare le funzionalità di stampa, invio email, download nei formati disponibili del (i) record.
Recursively enumerable sets and degrees : a study of computable functions and computably generated sets / Robert I. Soare
| Recursively enumerable sets and degrees : a study of computable functions and computably generated sets / Robert I. Soare |
| Autore | Soare, Robert Irving |
| Pubbl/distr/stampa | Berlin : Springer-Verlag, 1987 |
| Descrizione fisica | xviii, 437 p. ; 25 cm. |
| Disciplina | 511.3 |
| Collana | Perspectives in mathematical logic |
| Soggetto topico |
Computable functions
Recursive functions |
| ISBN | 3540152997 |
| Classificazione |
AMS 03D10
AMS 03D25 AMS 03D30 QA9.615.S63 |
| Formato | Materiale a stampa  |
| Livello bibliografico | Monografia |
| Lingua di pubblicazione | en |
| Record Nr. | UNISALENTO-991001291719707536 |
Soare, Robert Irving
|
||
| Berlin : Springer-Verlag, 1987 | ||
| Materiale a stampa | ||
| Lo trovi qui: Univ. del Salento | ||
| ||
Reverse mathematics : problems, reductions, and proofs / / Damir D. Dzhafarov, Carl Mummert
| Reverse mathematics : problems, reductions, and proofs / / Damir D. Dzhafarov, Carl Mummert |
| Autore | Dzhafarov Damir D. |
| Pubbl/distr/stampa | Cham, Switzerland : , : Springer, , [2022] |
| Descrizione fisica | 1 online resource (498 pages) |
| Disciplina | 511.3 |
| Collana | Theory and applications of computability |
| Soggetto topico |
Computable functions
Reverse mathematics |
| ISBN | 3-031-11367-5 |
| Formato | Materiale a stampa |
| Livello bibliografico | Monografia |
| Lingua di pubblicazione | eng |
| Nota di contenuto |
Intro -- Preface -- Acknowledgments -- Contents -- List of Figures -- Introduction -- What is reverse mathematics? -- Historical remarks -- Considerations about coding -- Philosophical implications -- Conventions and notation -- Part I Computable mathematics -- Computability theory -- The informal idea of computability -- Primitive recursive functions -- Some primitive recursive functions -- Bounded quantification -- Coding sequences with primitive recursion -- Turing computability -- Three key theorems -- Computably enumerable sets and the halting problem -- The arithmetical hierarchy and Post's theorem -- Relativization and oracles -- Trees and PA degrees -- Pi-0-1 classes -- Basis theorems -- PA degrees -- Exercises -- Instance-solution problems -- Problems -- Forall/exists theorems -- Multiple problem forms -- Represented spaces -- Representing R -- Complexity -- Uniformity -- Further examples -- Exercises -- Problem reducibilities -- Subproblems and identity reducibility -- Computable reducibility -- Weihrauch reducibility -- Strong forms -- Multiple applications -- Omega model reducibility -- Hirschfeldt-Jockusch games -- Exercises -- Part II Formalization and syntax -- Second order arithmetic -- Syntax and semantics -- Hierarchies of formulas -- Arithmetical formulas -- Analytical formulas -- Arithmetic -- First order arithmetic -- Second order arithmetic -- Formalization -- The subsystem RCAo -- Delta-0-1 comprehension -- Coding finite sets -- Formalizing computability theory -- The subsystems ACAo and WKLo -- The subsystem ACA0 -- The subsystem WKL0 -- Equivalences between mathematical principles -- The subsystems P11-CAo and ATRo -- The subsystem Pi-1-1-CA0 -- The subsystem ATR0 -- Conservation results -- First order parts of theories -- Comparing reducibility notions -- Full second order semantics -- Exercises -- Induction and bounding.
Induction, bounding, and least number principles -- Finiteness, cuts, and all that -- The Kirby-Paris hierarchy -- Reverse recursion theory -- Hirst's theorem and B-Sigma02 -- So, why Sigma-01 induction? -- Exercises -- Forcing -- A motivating example -- Notions of forcing -- Density and genericity -- The forcing relation -- Effective forcing -- Forcing in models -- Harrington's theorem and conservation -- Exercises -- Part III Combinatorics -- Ramsey's theorem -- Upper bounds -- Lower bounds -- Seetapun's theorem -- Stability and cohesiveness -- Stability -- Cohesiveness -- The Cholak-Jockusch-Slaman decomposition -- A different proof of Seetapun's theorem -- Other applications -- Liu's theorem -- Preliminaries -- Proof of Lemma 8.6.6 -- Proof of Lemma 8.6.7 -- The first order part of RT -- Two versus arbitrarily many colors -- Proof of Proposition 8.7.4 -- Proof of Proposition 8.7.5 -- What else is known? -- The SRT22 vs. COH problem -- Summary: Ramsey's theorem and the ``big five'' -- Exercises -- Other combinatorial principles -- Finer results about RT -- Ramsey's theorem for singletons -- Ramsey's theorem for higher exponents -- Homogeneity vs. limit homogeneity -- Partial and linear orders -- Equivalences and bounds -- Stable partial and linear orders -- Separations over RCA0 -- Variants under finer reducibilities -- Polarized Ramsey's theorem -- Rainbow Ramsey's theorem -- Erdős-Moser theorem -- The Chubb-Hirst-McNicholl tree theorem -- Milliken's tree theorem -- Thin set and free set theorems -- Hindman's theorem -- Apartness, gaps, and finite unions -- Towsner's simple proof -- Variants with bounded sums -- Applications of the Lovász local lemma -- Model theoretic and set theoretic principles -- Languages, theories, and models -- The atomic model theorem -- The finite intersection principle -- Weak weak König's lemma. The reverse mathematics zoo -- Exercises -- Part IV Other areas -- Analysis and topology -- Formalizations of the real line -- Sequences and convergence -- Sets and continuous functions -- Sets of points -- Continuous functions -- The intermediate value theorem -- Closed sets and compactness -- Separably closed sets -- Uniform continuity and boundedness -- Topological dynamics and ergodic theory -- Birkhoff's recurrence theorem -- The Auslander-Ellis theorem and iterated Hindman's theorem -- Measure theory and the mean ergodic theorem -- Additional results in real analysis -- Topology, MF spaces, CSC spaces -- Countable, second countable spaces -- MF spaces -- Reverse mathematics of MF spaces -- Exercises -- Algebra -- Groups, rings, and other structures -- Vector spaces and bases -- The complexity of ideals -- Orderability -- The Nielsen-Schreier theorem -- Other topics -- Exercises -- Set theory and beyond -- Well orderings and ordinals -- The Sigma-1-1 separation principle -- Comparability of well orderings -- Proof of Proposition 12.1.12 -- Descriptive set theory -- Determinacy -- Gale-Stewart games -- Clopen and open determinacy -- Gödel's constructible universe -- Friedman's theorem -- Higher order reverse mathematics -- Exercises -- References -- Index. |
| Record Nr. | UNISA-996483160303316 |
|
Dzhafarov Damir D.
|
||
| Cham, Switzerland : , : Springer, , [2022] | ||
| Materiale a stampa | ||
| Lo trovi qui: Univ. di Salerno | ||
| ||
Reverse mathematics : problems, reductions, and proofs / / Damir D. Dzhafarov, Carl Mummert
| Reverse mathematics : problems, reductions, and proofs / / Damir D. Dzhafarov, Carl Mummert |
| Autore | Dzhafarov Damir D. |
| Pubbl/distr/stampa | Cham, Switzerland : , : Springer, , [2022] |
| Descrizione fisica | 1 online resource (498 pages) |
| Disciplina | 511.3 |
| Collana | Theory and applications of computability |
| Soggetto topico |
Computable functions
Reverse mathematics |
| ISBN | 3-031-11367-5 |
| Formato | Materiale a stampa |
| Livello bibliografico | Monografia |
| Lingua di pubblicazione | eng |
| Nota di contenuto |
Intro -- Preface -- Acknowledgments -- Contents -- List of Figures -- Introduction -- What is reverse mathematics? -- Historical remarks -- Considerations about coding -- Philosophical implications -- Conventions and notation -- Part I Computable mathematics -- Computability theory -- The informal idea of computability -- Primitive recursive functions -- Some primitive recursive functions -- Bounded quantification -- Coding sequences with primitive recursion -- Turing computability -- Three key theorems -- Computably enumerable sets and the halting problem -- The arithmetical hierarchy and Post's theorem -- Relativization and oracles -- Trees and PA degrees -- Pi-0-1 classes -- Basis theorems -- PA degrees -- Exercises -- Instance-solution problems -- Problems -- Forall/exists theorems -- Multiple problem forms -- Represented spaces -- Representing R -- Complexity -- Uniformity -- Further examples -- Exercises -- Problem reducibilities -- Subproblems and identity reducibility -- Computable reducibility -- Weihrauch reducibility -- Strong forms -- Multiple applications -- Omega model reducibility -- Hirschfeldt-Jockusch games -- Exercises -- Part II Formalization and syntax -- Second order arithmetic -- Syntax and semantics -- Hierarchies of formulas -- Arithmetical formulas -- Analytical formulas -- Arithmetic -- First order arithmetic -- Second order arithmetic -- Formalization -- The subsystem RCAo -- Delta-0-1 comprehension -- Coding finite sets -- Formalizing computability theory -- The subsystems ACAo and WKLo -- The subsystem ACA0 -- The subsystem WKL0 -- Equivalences between mathematical principles -- The subsystems P11-CAo and ATRo -- The subsystem Pi-1-1-CA0 -- The subsystem ATR0 -- Conservation results -- First order parts of theories -- Comparing reducibility notions -- Full second order semantics -- Exercises -- Induction and bounding.
Induction, bounding, and least number principles -- Finiteness, cuts, and all that -- The Kirby-Paris hierarchy -- Reverse recursion theory -- Hirst's theorem and B-Sigma02 -- So, why Sigma-01 induction? -- Exercises -- Forcing -- A motivating example -- Notions of forcing -- Density and genericity -- The forcing relation -- Effective forcing -- Forcing in models -- Harrington's theorem and conservation -- Exercises -- Part III Combinatorics -- Ramsey's theorem -- Upper bounds -- Lower bounds -- Seetapun's theorem -- Stability and cohesiveness -- Stability -- Cohesiveness -- The Cholak-Jockusch-Slaman decomposition -- A different proof of Seetapun's theorem -- Other applications -- Liu's theorem -- Preliminaries -- Proof of Lemma 8.6.6 -- Proof of Lemma 8.6.7 -- The first order part of RT -- Two versus arbitrarily many colors -- Proof of Proposition 8.7.4 -- Proof of Proposition 8.7.5 -- What else is known? -- The SRT22 vs. COH problem -- Summary: Ramsey's theorem and the ``big five'' -- Exercises -- Other combinatorial principles -- Finer results about RT -- Ramsey's theorem for singletons -- Ramsey's theorem for higher exponents -- Homogeneity vs. limit homogeneity -- Partial and linear orders -- Equivalences and bounds -- Stable partial and linear orders -- Separations over RCA0 -- Variants under finer reducibilities -- Polarized Ramsey's theorem -- Rainbow Ramsey's theorem -- Erdős-Moser theorem -- The Chubb-Hirst-McNicholl tree theorem -- Milliken's tree theorem -- Thin set and free set theorems -- Hindman's theorem -- Apartness, gaps, and finite unions -- Towsner's simple proof -- Variants with bounded sums -- Applications of the Lovász local lemma -- Model theoretic and set theoretic principles -- Languages, theories, and models -- The atomic model theorem -- The finite intersection principle -- Weak weak König's lemma. The reverse mathematics zoo -- Exercises -- Part IV Other areas -- Analysis and topology -- Formalizations of the real line -- Sequences and convergence -- Sets and continuous functions -- Sets of points -- Continuous functions -- The intermediate value theorem -- Closed sets and compactness -- Separably closed sets -- Uniform continuity and boundedness -- Topological dynamics and ergodic theory -- Birkhoff's recurrence theorem -- The Auslander-Ellis theorem and iterated Hindman's theorem -- Measure theory and the mean ergodic theorem -- Additional results in real analysis -- Topology, MF spaces, CSC spaces -- Countable, second countable spaces -- MF spaces -- Reverse mathematics of MF spaces -- Exercises -- Algebra -- Groups, rings, and other structures -- Vector spaces and bases -- The complexity of ideals -- Orderability -- The Nielsen-Schreier theorem -- Other topics -- Exercises -- Set theory and beyond -- Well orderings and ordinals -- The Sigma-1-1 separation principle -- Comparability of well orderings -- Proof of Proposition 12.1.12 -- Descriptive set theory -- Determinacy -- Gale-Stewart games -- Clopen and open determinacy -- Gödel's constructible universe -- Friedman's theorem -- Higher order reverse mathematics -- Exercises -- References -- Index. |
| Record Nr. | UNINA-9910585784903321 |
|
Dzhafarov Damir D.
|
||
| Cham, Switzerland : , : Springer, , [2022] | ||
| Materiale a stampa | ||
| Lo trovi qui: Univ. Federico II | ||
| ||
Revolutions and revelations in computability : 18th Conference on Computability in Europe, CiE 2022, Swansea, UK, July 11-15, 2022 : proceedings / / Ulrich Berger [and three others], editors
| Revolutions and revelations in computability : 18th Conference on Computability in Europe, CiE 2022, Swansea, UK, July 11-15, 2022 : proceedings / / Ulrich Berger [and three others], editors |
| Pubbl/distr/stampa | Cham, Switzerland : , : Springer Nature Switzerland AG, , [2022] |
| Descrizione fisica | 1 online resource (374 pages) |
| Disciplina | 511.3 |
| Collana | Lecture notes in computer science |
| Soggetto topico |
Computable functions
Computer science - Mathematics Funcions computables Informàtica |
| Soggetto genere / forma |
Congressos
Llibres electrònics |
| ISBN | 3-031-08740-2 |
| Formato | Materiale a stampa |
| Livello bibliografico | Monografia |
| Lingua di pubblicazione | eng |
| Record Nr. | UNISA-996478858103316 |
| Cham, Switzerland : , : Springer Nature Switzerland AG, , [2022] | ||
| Materiale a stampa | ||
| Lo trovi qui: Univ. di Salerno | ||
| ||
Revolutions and revelations in computability : 18th Conference on Computability in Europe, CiE 2022, Swansea, UK, July 11-15, 2022 : proceedings / / Ulrich Berger [and three others], editors
| Revolutions and revelations in computability : 18th Conference on Computability in Europe, CiE 2022, Swansea, UK, July 11-15, 2022 : proceedings / / Ulrich Berger [and three others], editors |
| Pubbl/distr/stampa | Cham, Switzerland : , : Springer Nature Switzerland AG, , [2022] |
| Descrizione fisica | 1 online resource (374 pages) |
| Disciplina | 511.3 |
| Collana | Lecture notes in computer science |
| Soggetto topico |
Computable functions
Computer science - Mathematics Funcions computables Informàtica |
| Soggetto genere / forma |
Congressos
Llibres electrònics |
| ISBN | 3-031-08740-2 |
| Formato | Materiale a stampa |
| Livello bibliografico | Monografia |
| Lingua di pubblicazione | eng |
| Record Nr. | UNINA-9910580155403321 |
| Cham, Switzerland : , : Springer Nature Switzerland AG, , [2022] | ||
| Materiale a stampa | ||
| Lo trovi qui: Univ. Federico II | ||
| ||
STOC '15 : proceedings of the 47th ACM Symposium on Theory of Computing Conference : June 14-17, 2015, Portland, OR, USA / / sponsored by ACM SIGACT
| STOC '15 : proceedings of the 47th ACM Symposium on Theory of Computing Conference : June 14-17, 2015, Portland, OR, USA / / sponsored by ACM SIGACT |
| Pubbl/distr/stampa | New York : , : ACM, , 2015 |
| Descrizione fisica | 1 online resource (900 pages) |
| Disciplina | 004.0151 |
| Soggetto topico |
Computer science - Mathematics
Computable functions |
| Soggetto genere / forma | Electronic books. |
| Formato | Materiale a stampa |
| Livello bibliografico | Monografia |
| Lingua di pubblicazione | eng |
| Altri titoli varianti |
Symposium on Theory of Computing '15 : proceedings of the forty-seventh Association for Computing Machinery Symposium on Theory of Computing Conference : June 14-17, 2015, Portland, Oregon, United States of America
Symposium on Theory of Computing 2015 Proceedings of the forty-seventh annual ACM symposium on Theory of computing Proceedings of the forty-seventh annual Association for Computing Machinery symposium on Theory of computing |
| Record Nr. | UNINA-9910376606103321 |
| New York : , : ACM, , 2015 | ||
| Materiale a stampa | ||
| Lo trovi qui: Univ. Federico II | ||
| ||
Theory of computation [[electronic resource] /] / George Tourlakis
| Theory of computation [[electronic resource] /] / George Tourlakis |
| Autore | Tourlakis George J |
| Pubbl/distr/stampa | Hoboken, N.J., : Wiley, 2012 |
| Descrizione fisica | 1 online resource (410 p.) |
| Disciplina | 511.3/52 |
| Soggetto topico |
Computable functions
Functional programming languages |
| ISBN |
1-280-59246-X
9786613622297 1-118-31535-9 1-118-31536-7 1-118-31533-2 |
| Classificazione | MAT008000 |
| Formato | Materiale a stampa |
| Livello bibliografico | Monografia |
| Lingua di pubblicazione | eng |
| Nota di contenuto |
Theory of Computation; CONTENTS; Preface; 1 Mathematical Foundations; 1.1 Sets and Logic; Naïvely; 1.1.1 A Detour via Logic; 1.1.2 Sets and their Operations; 1.1.3 Alphabets, Strings and Languages; 1.2 Relations and Functions; 1.3 Big and Small Infinite Sets; Diagonalization; 1.4 Induction from a User's Perspective; 1.4.1 Complete, or Course-of-Values, Induction; 1.4.2 Simple Induction; 1.4.3 The Least Principle; 1.4.4 The Equivalence of Induction and the Least Principle; 1.5 Why Induction Ticks; 1.6 Inductively Defined Sets; 1.7 Recursive Definitions of Functions; 1.8 Additional Exercises
2 Algorithms, Computable Functions and Computations 2.1 A Theory of Computability; 2.1.1 A Programming Framework for Computable Functions; 2.1.2 Primitive Recursive Functions; 2.1.3 Simultaneous Primitive Recursion; 2.1.4 Pairing Functions; 2.1.5 Iteration; 2.2 A Programming Formalism for the Primitive Recursive Functions; 2.2.1 PR vs. L; 2.2.2 Incompleteness of PR; 2.3 URM Computations and their Arithmetization; 2.4 A Double Recursion that Leads Outside the Primitive Recursive Function Class; 2.4.1 The Ackermann Function; 2.4.2 Properties of the Ackermann Function 2.4.3 The Ackermann Function Majorizes All the Functions of PR 2.4.4 The Graph of the Ackermann Function is in PR*; 2.5 Semi-computable Relations; Unsolvability; 2.6 The Iteration Theorem of Kleene; 2.7 Diagonalization Revisited; Unsolvability via Reductions; 2.7.1 More Diagonalization; 2.7.2 Reducibility via the S-m-n Theorem; 2.7.3 More Dovetailing; 2.7.4 Recursive Enumerations; 2.8 Productive and Creative Sets; 2.9 The Recursion Theorem; 2.9.1 Applications of the Recursion Theorem; 2.10 Completeness; 2.11 Unprovability from Unsolvability 3.5 Additional Exercises 4 Adding a Stack to a NFA: Pushdown Automata; 4.1 The PDA; 4.2 PDA Computations; 4.2.1 ES vs AS vs ES+AS; 4.3 The PDA-acceptable Languages are the Context Free Languages; 4.4 Non Context Free Languages; Another Pumping Lemma; 4.5 Additional Exercises; 5 Computational Complexity; 5.1 Adding a Second Stack; Turing Machines; 5.1.1 Turing Machines; 5.1.2 N P-Completeness; 5.1.3 Cook's Theorem; 5.2 Axt, Loop Program, and Grzegorczyk Hierarchies; 5.3 Additional Exercises; Bibliography; Index |
| Record Nr. | UNINA-9910141450503321 |
|
Tourlakis George J
|
||
| Hoboken, N.J., : Wiley, 2012 | ||
| Materiale a stampa | ||
| Lo trovi qui: Univ. Federico II | ||
| ||
Theory of computation [[electronic resource] /] / George Tourlakis
| Theory of computation [[electronic resource] /] / George Tourlakis |
| Autore | Tourlakis George J |
| Pubbl/distr/stampa | Hoboken, N.J., : Wiley, 2012 |
| Descrizione fisica | 1 online resource (410 p.) |
| Disciplina | 511.3/52 |
| Soggetto topico |
Computable functions
Functional programming languages |
| ISBN |
1-280-59246-X
9786613622297 1-118-31535-9 1-118-31536-7 1-118-31533-2 |
| Classificazione | MAT008000 |
| Formato | Materiale a stampa |
| Livello bibliografico | Monografia |
| Lingua di pubblicazione | eng |
| Nota di contenuto |
Theory of Computation; CONTENTS; Preface; 1 Mathematical Foundations; 1.1 Sets and Logic; Naïvely; 1.1.1 A Detour via Logic; 1.1.2 Sets and their Operations; 1.1.3 Alphabets, Strings and Languages; 1.2 Relations and Functions; 1.3 Big and Small Infinite Sets; Diagonalization; 1.4 Induction from a User's Perspective; 1.4.1 Complete, or Course-of-Values, Induction; 1.4.2 Simple Induction; 1.4.3 The Least Principle; 1.4.4 The Equivalence of Induction and the Least Principle; 1.5 Why Induction Ticks; 1.6 Inductively Defined Sets; 1.7 Recursive Definitions of Functions; 1.8 Additional Exercises
2 Algorithms, Computable Functions and Computations 2.1 A Theory of Computability; 2.1.1 A Programming Framework for Computable Functions; 2.1.2 Primitive Recursive Functions; 2.1.3 Simultaneous Primitive Recursion; 2.1.4 Pairing Functions; 2.1.5 Iteration; 2.2 A Programming Formalism for the Primitive Recursive Functions; 2.2.1 PR vs. L; 2.2.2 Incompleteness of PR; 2.3 URM Computations and their Arithmetization; 2.4 A Double Recursion that Leads Outside the Primitive Recursive Function Class; 2.4.1 The Ackermann Function; 2.4.2 Properties of the Ackermann Function 2.4.3 The Ackermann Function Majorizes All the Functions of PR 2.4.4 The Graph of the Ackermann Function is in PR*; 2.5 Semi-computable Relations; Unsolvability; 2.6 The Iteration Theorem of Kleene; 2.7 Diagonalization Revisited; Unsolvability via Reductions; 2.7.1 More Diagonalization; 2.7.2 Reducibility via the S-m-n Theorem; 2.7.3 More Dovetailing; 2.7.4 Recursive Enumerations; 2.8 Productive and Creative Sets; 2.9 The Recursion Theorem; 2.9.1 Applications of the Recursion Theorem; 2.10 Completeness; 2.11 Unprovability from Unsolvability 3.5 Additional Exercises 4 Adding a Stack to a NFA: Pushdown Automata; 4.1 The PDA; 4.2 PDA Computations; 4.2.1 ES vs AS vs ES+AS; 4.3 The PDA-acceptable Languages are the Context Free Languages; 4.4 Non Context Free Languages; Another Pumping Lemma; 4.5 Additional Exercises; 5 Computational Complexity; 5.1 Adding a Second Stack; Turing Machines; 5.1.1 Turing Machines; 5.1.2 N P-Completeness; 5.1.3 Cook's Theorem; 5.2 Axt, Loop Program, and Grzegorczyk Hierarchies; 5.3 Additional Exercises; Bibliography; Index |
| Record Nr. | UNINA-9910824075303321 |
|
Tourlakis George J
|
||
| Hoboken, N.J., : Wiley, 2012 | ||
| Materiale a stampa | ||
| Lo trovi qui: Univ. Federico II | ||
| ||
