Elementar computability theory
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.
- Computability. Logic, reasoning, computer and Assembler, infinity, limits of automatizability. Textbook for class-room and self-study
- EAGLE start-up aid. Theory of computability. Cantor diagonalization, Gödelization, Turing machines
- The intensional content of Rice's theorem
- scientific article; zbMATH DE number 5778850 (Why is no real title available?)
- scientific article; zbMATH DE number 530148 (Why is no real title available?)
- scientific article; zbMATH DE number 572102 (Why is no real title available?)
- scientific article; zbMATH DE number 3992928 (Why is no real title available?)
- Introduction to computability
- Computability
- A mathematical primer on computability
- scientific article; zbMATH DE number 225477 (Why is no real title available?)
This page was built for publication: Elementar computability theory
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1911231)
