000			04087nam a2200385 i 4500
999			_c398072 _d398072 _x1
001			398072
003			ES-MaUEC
005			20240429180330.0
006			a|||||o|||| 00| 0
007			cr nn 008mamaa
008			230523s2023 sz | o |||| 0|eng d
020			_a9783031269042
024	7		_a10.1007/978-3-031-26904-2 _2doi
040			_aES-MaUEC _bspa _cES-MaUEC _dES-MaUEC
050		4	_aQA76.9 .M35 _b2023 EB
100	1		_aSupowit, Kenneth Jay _d1957- _eautor _4http://id.loc.gov/vocabulary/relators/aut _9689531
245	1	0	_aAlgorithms for Constructing Computably Enumerable Sets _cby Kenneth J. Supowit
250			_a1st ed 2023
264		1	_aCham _bSpringer International Publishing _c2023
300			_a1 recurso en línea
336			_atexto _btxt _2rdacontent
337			_aelectrónico _bc _2rdamedia
338			_arecurso electrónico _bcr _2rdacarrier
347			_atext file _bPDF _2rda
490	0		_aComputer Science Foundations and Applied Logic _x2731-5762
505	0		_a1 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.
520			_aLogicians have developed beautiful algorithmic techniques for the construction of computably enumerable sets. This textbook presents these techniques in a unified way that should appeal to computer scientists. Specifically, the book explains, organizes, and compares various algorithmic techniques used in computability theory (which was formerly called "classical recursion theory"). This area of study has produced some of the most beautiful and subtle algorithms ever developed for any problems. These algorithms are little-known outside of a niche within the mathematical logic community. By presenting them in a style familiar to computer scientists, the intent is to greatly broaden their influence and appeal. Topics and features: · All other books in this field focus on the mathematical results, rather than on the algorithms. · There are many exercises here, most of which relate to details of the algorithms. · The proofs involving priority trees are written here in greater detail, and with more intuition, than can be found elsewhere in the literature. · The algorithms are presented in a pseudocode very similar to that used in textbooks (such as that by Cormen, Leiserson, Rivest, and Stein) on concrete algorithms. · In addition to their aesthetic value, the algorithmic ideas developed for these abstract problems might find applications in more practical areas. Graduate students in computer science or in mathematical logic constitute the primary audience. Furthermore, when the author taught a one-semester graduate course based on this material, a number of advanced undergraduates, majoring in computer science or mathematics or both, took the course and flourished in it. Kenneth J. Supowit is an Associate Professor Emeritus, Department of Computer Science & Engineering, Ohio State University, Columbus, Ohio, US.
988			_aSpringer_Computer_2023
650		7	_2embne _9160233 _aMatemáticas discretas
856	4	0	_uhttps://go.openathens.net/redirector/universidadeuropea.es?url=https://doi.org/10.1007/978-3-031-26904-2 _zAcceso a este recurso digital (usuarios Universidad Europea de Madrid)
942			_2lcc _cLE
998			_b02/2024 _dz _eb _zSI