What can be computed? : a practical guide to the theory of computation / John MacCormick.
What Can Be Computed? is a uniquely accessible yet rigorous introduction to the most profound ideas at the heart of computer science. Crafted specifically for undergraduates who are studying the subject for the first time, and requiring minimal prerequisites, the book focuses on the essential fundam...
| Main Author: | |
|---|---|
| Language: | English |
| Published: |
Princeton, New Jersey :
Princeton University Press,
[2018]
|
| Subjects: | |
| Genre: | |
| Physical Description: | xix, 383 pages ; 27 cm |
| Format: | Book |
Contents:
- Introduction: what can and cannot be computed?
- What is a computer program?
- Some impossible Python programs
- What is a computational problem?
- Turing machines: the simplest computers
- Universal computer programs: programs that can do anything
- Reductions: how to prove a problem is hard
- Nondeterminism: magic or reality?
- Finite automata: computing with limited resources
- Complexity theory: when efficiency does matter
- Poly and Expo: the two most fundamental complexity classes
- PolyCheck and NPoly: hard problems that are easy to verify
- Polynomial-time mapping reductions: proving x is as easy as y
- NP-completeness: most hard problems are equally hard
- The original Turing machine
- You can't prove everything that's true
- Karp's 21 problems
- Conclusion: what will be computed?