Limits Of Computation: From A Programming Perspective (undergraduate Topics In Computer Science)
by Bernhard Reus /
2016 / English / PDF
7.5 MB Download
This textbook discusses the most fundamental and puzzling
questions about the foundations of computing. In 23 lecture-sized
chapters it provides an exciting tour through the most important
results in the field of computability and time complexity,
including the Halting Problem, Rice's Theorem, Kleene's Recursion
Theorem, the Church-Turing Thesis, Hierarchy Theorems, and
Cook-Levin's Theorem. Each chapter contains classroom-tested
material, including examples and exercises. Links between
adjacent chapters provide a coherent narrative.
This textbook discusses the most fundamental and puzzling
questions about the foundations of computing. In 23 lecture-sized
chapters it provides an exciting tour through the most important
results in the field of computability and time complexity,
including the Halting Problem, Rice's Theorem, Kleene's Recursion
Theorem, the Church-Turing Thesis, Hierarchy Theorems, and
Cook-Levin's Theorem. Each chapter contains classroom-tested
material, including examples and exercises. Links between
adjacent chapters provide a coherent narrative.Fundamental results are explained lucidly by means of programs
written in a simple, high-level imperative programming language,
which only requires basic mathematical knowledge. Throughout the
book, the impact of the presented results on the entire field of
computer science is emphasised. Examples range from program
analysis to networking, from database programming to popular games
and puzzles. Numerous biographical footnotes about the famous
scientists who developed the subject are also included.
Fundamental results are explained lucidly by means of programs
written in a simple, high-level imperative programming language,
which only requires basic mathematical knowledge. Throughout the
book, the impact of the presented results on the entire field of
computer science is emphasised. Examples range from program
analysis to networking, from database programming to popular games
and puzzles. Numerous biographical footnotes about the famous
scientists who developed the subject are also included."Limits of Computation"
"Limits of Computation" offers a thorough, yet accessible,
introduction to computability and complexity for the computer
science student of the 21st century.
offers a thorough, yet accessible,
introduction to computability and complexity for the computer
science student of the 21st century.