Introduction to Computability Theory (2nd Edition)

Author: (American) Sipser, translated by Tang Changjie et al.
Publisher:
Publishing Time:
Features: This book is a classic in the field of theoretical computer science and has been adopted as a textbook by many universities abroad. It is characterized by its emphasis on thinking and in-depth guidance, systematically introducing the three main components of computer theory: automata and languages, computability theory, and computational complexity theory. Additionally, it provides detailed explanations of some advanced topics in computability and computational complexity theory. Throughout the book, readers are guided to tackle high-level problems in this field through thought-provoking questions, exciting results, and open problems. A significant highlight of the new edition is the inclusion of more exercises, teaching materials, and selected solutions, making it even more suitable for teaching. The book is written in a clear and progressive manner, with appropriate depth and emphasis, avoiding excessive technical details. It can serve as a textbook for senior undergraduate and graduate students in computer science, as well as a reference for faculty and researchers in related fields.