top

  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.

  Info

  • Utilizzare questo link per rimuovere la selezione effettuata.
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
Opac: Controlla la disponibilità qui
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
Opac: Controlla la disponibilità qui
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
Opac: Controlla la disponibilità qui
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
Opac: Controlla la disponibilità qui
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
Opac: Controlla la disponibilità qui
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
Opac: Controlla la disponibilità qui
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
Opac: Controlla la disponibilità qui
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
Opac: Controlla la disponibilità qui