scientific article; zbMATH DE number 225477
The book is intended for use as a textbook for introduction courses covering Computability Theory. The course is taught to Computer Science students nor for mathematicians. And this is the main advantage of the book in contrast to many other ones in this field. The presentation is quite informal preserving, however, the elegance of mathematical proofs. The book introduces basic models of computation: Turing machines, Post machines, unlimited register machines, Markov algorithms, nondeterministic and probabilistic Turing machines. Subjects covered include: universality, undecidability, Post Correspondence Problem (including the matrix mortality problem) and basic facts from the Recursive Function Theory such as \(s\)-\(m\)-\(n\) and Rice theorems. The last three sections present an informal look to Gödel's Incompleteness Theorem and the Church-Turing hypothesis. Computer Science students would find this book as an elegant and informal introduction to basic facts of the Computability Theory.
- Models of computation. An introduction to computability theory
- The concept of computability
- Elementar computability theory
- The complexity of agent design problems: Determinism and history dependence
- Computability. Turing, Gödel, Church, and beyond
- Turing computability. Theory and applications
- Computability theory
- 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
- Computability Results Used in Differential Geometry
- Introduction to algorithm theory
- Bounding homogenous models
- The Foundations of Computability Theory
- Computable Models
- scientific article; zbMATH DE number 5778850 (Why is no real title available?)
- The degree spectra of homogeneous models
- Promptness does not imply superlow cuppability
- scientific article; zbMATH DE number 4088936 (Why is no real title available?)
- scientific article; zbMATH DE number 47306 (Why is no real title available?)
- scientific article; zbMATH DE number 107969 (Why is no real title available?)
- scientific article; zbMATH DE number 1344905 (Why is no real title available?)
- scientific article; zbMATH DE number 530148 (Why is no real title available?)
- An elementary introduction to the theory of Turing machines. Incl. 1 disk
- scientific article; zbMATH DE number 1955470 (Why is no real title available?)
- scientific article; zbMATH DE number 1560883 (Why is no real title available?)
- Turing machines: universality and limits of computational power
- Introduction to computability
- A characterization of the \(0\)-basis homogeneous bounding degrees
- The Foundations of Computability Theory
- Computability. Models of computation and undecidability
- Limits of computation. From a programming perspective
- A mathematical primer on computability
- scientific article; zbMATH DE number 5194318 (Why is no real title available?)
- The settling-time reducibility ordering
- Computability and complexity theory.
This page was built for publication:
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5286632)