Algorithms for Constructing Computably Enumerable Sets

ISBN-13: 9783031269035 / Angielski

Kenneth J. Supowit

Opis

Logicians 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.

Spis treści

Preface

1 History

2 This book

3 Acknowledgements

4 A truth universally acknowledged

1 Notation and terms

1 Index of notation and terms

2 Defaults

3 Notes about the pseudo-code

4 Miscellaneous notes about the text

2 Set theory, requirements, witnesses

1 Infinite cardinals

2 Infinitely many infinite cardinals

3 What’s new in this chapter?

4 Exercises

3 Computable and c.e. sets

1 Turing machines

2 Computably enumerable, computable

3 An example of a c.e.n. set

4 What’s new in this chapter?

5 Afternotes

6 Exercises

4 Priorities (a splitting theorem)

1 A priority argument

2 What’s new in this chapter?

3 Afternotes

4 Exercises

5 Reductions, comparability (Kleene-Post Theorem)

1 Oracle Turing machines

2 Turing reductions

3 The theorem

4 What’s new in this chapter?

5 Afternotes

6 Exercises

6 Finite injury (Friedberg-Muchnik Theorem)

1 The theorem

2 What’s new in this chapter?

3 Afternotes

4 Exercises

7 The Permanence Lemma

1 Exercises

8 Permitting (Friedberg-Muchnik below C Theorem)

1 The Lemma

2 The theorem

3 Valid witnesses

4 Types of witnesses

5 The algorithm

6 Verification

7 What’s new in this chapter?

8 Afternotes

9 Exercises

9 Length of agreement (Sacks Splitting Theorem)

1 Definitions and main idea

2 The theorem

3 More definitions

4 The algorithm

5 Verification

6 Why preserve similarities?

7 What’s new in this chapter?

8 Afternotes

9 Exercises . .

10 Introduction to infinite injury

1 A review of finite injury priority arguments

2 Coping with infinite injury

3 Afternotes

11 A tree of guesses (Weak Thickness Lemma)

1 Definitions

2 The “lemma”

3 The tree

4 More definitions

5 The algorithm

6 Verification

7 What’s new in this chapter?

8 Afternotes

9 Exercises

12 An infinitely branching tree (Thickness Lemma)

1 The tree .

2 Definitions

3 The algorithm

4 Verification .

5 What’s new in this chapter?

6 Afternotes

7 Exercises

13 True stages (another proof of the Thickness Lemma)

1 Definitions

2 The algorithm

3 Verification

4 What’s new in this chapter?

5 Afternotes

6 Exercises

14 Joint custody (Minimal Pair Theorem)

1 The theorem

2 The tree .

3 Definitions

4 Interpretation of the guesses

5 The algorithm

6 Verification .

7 What’s new in this chapter?

8 Afternotes

9 Exercises

15 Witness lists (Density Theorem)

1 The tree

2 Definitions

3 The algorithm

3.1 Main code

3.2 Subroutines

3.3 Notes on the algorithm

4 Verification

4.1 More definitions

4.2 Interpretation of the guesses

4.3 Facts

4.4 Lemmas

5 What’s new in this chapter?

6 Designing an algorithm

7 Afternotes

8 Exercises

16 The theme of this book: delaying tactics

Appendix A: a pairing function

Bibliography

1 Books

2 Articles

Solutions to selected exercises

O autorze

I received an A.B. degree in linguistics from Cornell University in 1978, and a Ph. D. in computer science from the University of Illinois in 1981.  Then I worked three years for Hewlett-Packard in Palo Alto, California.  Subsequently, I taught for four years at Princeton University, and then 34 years at Ohio State University, where I retired in May, 2022, and now have emeritus status.  Along the way, I’ve consulted for IBM, AT&T, Hewlett-Packard, and various small companies.

My research has primarily been in the analysis of algorithms, however, I’ve long been fascinated by computability theory, which has been the focus of my research and much of my teaching in recent years.  In Autumn, 2021, I taught a graduate level course using an earlier draft of this book as the text.