Algorithms for Constructing Computably Enumerable Sets

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.

邏輯學家已經開發出了用於構建可計算可枚舉集合的優美算法技術。這本教科書以統一的方式呈現這些技術，應該會吸引計算機科學家的興趣。

具體而言，本書解釋、組織和比較了在可計算性理論（以前稱為“經典遞歸理論”）中使用的各種算法技術。這個研究領域產生了一些最美麗和微妙的算法，用於解決各種問題。這些算法在數學邏輯社區以外鮮為人知。通過以計算機科學家熟悉的風格呈現它們，意圖大大擴大它們的影響力和吸引力。

主題和特點：
- 這個領域的其他書籍都專注於數學結果，而不是算法。
- 這裡有很多練習題，其中大部分與算法的細節有關。
- 這裡對涉及優先級樹的證明進行了更詳細的描述，並提供了比文獻中其他地方更多的直觀解釋。
- 算法以與具體算法教科書（如Cormen、Leiserson、Rivest和Stein的教科書）中使用的偽代碼非常相似的方式呈現。
- 除了其美學價值外，為這些抽象問題開發的算法思想可能在更實際的領域中找到應用。

計算機科學或數學邏輯的研究生是主要的受眾。此外，當作者基於這些材料教授了一學期的研究生課程時，有一些主修計算機科學或數學或兩者兼修的高年級本科生參加了課程並取得了良好的成績。

Kenneth J. Supowit是俄亥俄州立大學哥倫布分校計算機科學與工程系的名譽副教授，位於美國俄亥俄州哥倫布市。

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.

我於1978年從康奈爾大學獲得語言學的學士學位，並於1981年從伊利諾伊大學獲得計算機科學的博士學位。之後，我在加利福尼亞州帕羅奧圖的惠普公司工作了三年。隨後，我在普林斯頓大學教授了四年，然後在俄亥俄州立大學教授了34年，並於2022年5月退休，現在擁有名譽教授的地位。在此期間，我曾為IBM、AT&T、惠普和其他一些小公司提供諮詢服務。

我的研究主要集中在算法分析上，然而，我長期以來一直對可計算性理論深感興趣，這成為我近年來研究和教學的重點。在2021年秋季，我以本書的早期草稿作為教材，教授了一門研究生課程。