Elementar computability theory (Q1911231)

This is a concise introduction into fundamental concepts and results of computability theory. The approach is based on the language of while-programs for register machines over natural numbers. A first part (chapters 1-7) deals with the basic notations concerning the while-computability of functions, with gödelization, universal programs, Kleene's normal form, the halting problem, and Rice's theorem. In a second part (chapters 8-10), \(\mu\)-recursivity and Turing machines are defined and shown to be equivalent to while-programs. Moreover, Church's thesis is discussed, and basic relationships between computability, decidability and enumerability are treated. A final part (chapters 11-13) shows the unsolvability of Post's correspondence problem as well as the undecidability of first-order logic and of some problems connected with contextfree grammars. The book is self-contained and gives complete proofs of many basic results. For some applications and further results, sketches of proofs are given. To demonstrate the scope and the way of the presentation, we remark that even if Rice's theorem is proved, neither the s-m-n theorem nor the fixed point theorem are explicitely mentioned. The few shortcomings of the text are easily reparable. Thus, this book could well serve as both a basis and a textbook for an introductory course on the theory of computability.