What Can Be Computed?

An accessible and rigorous textbook for introducing undergraduates to computer science theory

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 es...

(展开全部)

An accessible and rigorous textbook for introducing undergraduates to computer science theory

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 fundamentals of computer science theory and features a practical approach that uses real computer programs (Python and Java) and encourages active experimentation. It is also ideal for self-study and reference.

The book covers the standard topics in the theory of computation, including Turing machines and finite automata, universal computation, nondeterminism, Turing and Karp reductions, undecidability, time-complexity classes such as P and NP, and NP-completeness, including the Cook-Levin Theorem. But the book also provides a broader view of computer science and its historical development, with discussions of Turing's original 1936 computing machines, the connections between undecidability and Gödel's incompleteness theorem, and Karp's famous set of twenty-one NP-complete problems.

Throughout, the book recasts traditional computer science concepts by considering how computer programs are used to solve real problems. Standard theorems are stated and proven with full mathematical rigor, but motivation and understanding are enhanced by considering concrete implementations. The book's examples and other content allow readers to view demonstrations of―and to experiment with―a wide selection of the topics it covers. The result is an ideal text for an introduction to the theory of computation.

An accessible and rigorous introduction to the essential fundamentals of computer science theory, written specifically for undergraduates taking introduction to the theory of computation

Features a practical, interactive approach using real computer programs (Python in the text, with forthcoming Java alternatives online) to enhance motivation and understanding

Gives equal emphasis to computability and complexity

Includes special topics that demonstrate the profound nature of key ideas in the theory of computation

Lecture slides and Python programs are available at whatcanbecomputed.com

John MacCormick is associate professor of computer science at Dickinson College and a leading teacher, researcher, and writer in his field. He has a PhD in computer vision from the University of Oxford and has worked in the research labs of Hewlett-Packard and Microsoft. His previous books include Nine Algorithms That Changed the Future: The Ingenious Ideas That Drive Today's C...

(展开全部)

John MacCormick is associate professor of computer science at Dickinson College and a leading teacher, researcher, and writer in his field. He has a PhD in computer vision from the University of Oxford and has worked in the research labs of Hewlett-Packard and Microsoft. His previous books include Nine Algorithms That Changed the Future: The Ingenious Ideas That Drive Today's Computers (Princeton). Erik Demaine and Martin Demaine created the curved crease sculpture featured on the cover of What Can Be Computed? Cover photo courtesy of the artists.

OVERVIEW
1 INTRODUCTION: WHAT CAN AND CANNOT BE COMPUTED?
1.1 Tractable problems
1.2 Intractable problems
1.3 Uncomputable problems
1.4 A more detailed overview of the book
· · · · · · (更多)

OVERVIEW
1 INTRODUCTION: WHAT CAN AND CANNOT BE COMPUTED?
1.1 Tractable problems
1.2 Intractable problems
1.3 Uncomputable problems
1.4 A more detailed overview of the book
1.5 Prerequisites for understanding this book
1.6 The goals of the book
1.7 Why study the theory of computation?
Part I: COMPUTABILITY THEORY
2 WHAT IS A COMPUTER PROGRAM?
2.1 Some Python program basics
2.2 SISO Python programs
2.3 ASCII characters and multiline strings
2.4 Some problematic programs
2.5 Formal definition of Python program
2.6 Decision programs and equivalent programs
2.7 Real-world programs versus SISO Python programs
3 SOME IMPOSSIBLE PYTHON PROGRAMS
3.1 Proof by contradiction
3.2 Programs that analyze other programs
3.3 The program yesOnString.py
3.4 The program yesOnSelf.py
3.5 The program notYesOnSelf.py
3.6 yesOnString.py can’t exist either
3.7 Perfect bug-finding programs are impossible
3.8 We can still find bugs, but we can’t do it perfectly
4 WHAT IS A COMPUTATIONAL PROBLEM?
4.1 Graphs, alphabets, strings, and languages
4.2 Defining computational problems
4.3 Categories of computational problems
4.4 The formal definition of “solving” a problem
4.5 Recognizing and deciding languages
5 TURING MACHINES: THE SIMPLEST COMPUTERS
5.1 Definition of a Turing machine
5.2 Some nontrivial Turing machines
5.3 From single-tape Turing machines to multi-tape Turing machines
5.4 From multi-tape Turing machines to Python programs and beyond
5.5 Going back the other way: Simulating a Turing machine with Python
5.6 Classical computers can simulate quantum computers
5.7 All known computers are Turing equivalent
6 UNIVERSAL COMPUTER PROGRAMS: PROGRAMS THAT CAN DO ANYTHING
6.1 Universal Python programs
6.2 Universal Turing machines
6.3 Universal computation in the real world
6.4 Programs that alter other programs
6.5 Problems that are undecidable but recognizable
7 REDUCTIONS: HOW TO PROVE A PROBLEM IS HARD
7.1 A reduction for easiness
7.2 A reduction for hardness
7.3 Formal definition of Turing reduction
7.4 Properties of Turing reductions
7.5 An abundance of uncomputable problems
7.6 Even more uncomputable problems
7.7 Uncomputable problems that aren’t about programs
7.8 Not every question about programs is uncomputable
7.9 Proof techniques for uncomputability
8 NONDETERMINISM: MAGIC OR REALITY?
8.1 Nondeterministic Python programs
8.2 Nondeterministic programs for nondecision problems
8.3 Computation trees
8.4 Nondeterminism doesn’t change what is computable
8.5 Nondeterministic Turing machines
8.6 Formal definition of nondeterministic Turing machines
8.7 Models of nondeterminism
8.8 Unrecognizable problems
8.9 Why study nondeterminism?
9 FINITE AUTOMATA: COMPUTING WITH LIMITED RESOURCES
9.1 Deterministic finite automata
9.2 Nondeterministic finite automata
9.3 Equivalence of nfas and dfas
9.4 Regular expressions
9.5 Some languages aren’t regular
9.6 Many more nonregular languages
9.7 Combining regular languages
Part II: COMPUTATIONAL COMPLEXITY THEORY
10 COMPLEXITY THEORY: WHEN EFFICIENCY DOES MATTER
10.1 Complexity theory uses asymptotic running times
10.2 Big-O notation
10.3 The running time of a program
10.4 Fundamentals of determining time complexity
10.5 For complexity, the computational model does matter
10.6 Complexity classes
11 Poly AND Expo: THE TWO MOST FUNDAMENTAL COMPLEXITY CLASSES
11.1 Definitions of Poly and Expo
11.2 Poly is a subset of Expo
11.3 A first look at the boundary between Poly and Expo
11.4 Poly and Expo don’t care about the computational model
11.5 HALTEx: A decision problem in Expo but not Poly
11.6 Other problems that are outside Poly
11.7 Unreasonable encodings of the input affect complexity
11.8 Why study Poly, really?
12 PolyCheck AND NPoly: HARD PROBLEMS THAT ARE EASY TO VERIFY
12.1 Verifiers
12.2 Polytime verifiers
12.3 The complexity class PolyCheck
12.4 The complexity class NPoly
12.5 PolyCheck and NPoly are identical
12.6 The PolyCheck/NPoly sandwich
12.7 Nondeterminism does seem to change what is computable efficiently
12.8 The fine print about NPoly
13 POLYNOMIAL-TIME MAPPING REDUCTIONS: PROVING X IS AS EASY AS Y
13.1 Definition of polytime mapping reductions
13.2 The meaning of polynomial-time mapping reductions
13.3 Proof techniques for polyreductions
13.4 Examples of polyreductions using Hamilton cycles
13.5 Three satisfiability problems: CIRCUITSAT, SAT, and 3-SAT
13.6 Polyreductions between CIRCUITSAT, SAT, and 3-SAT
13.7 Polyequivalence and its consequences
14 NP-COMPLETENESS: MOST HARD PROBLEMS ARE EQUALLY HARD
14.1 P versus NP
14.2 NP-completeness
14.3 NP-hardness
14.4 Consequences of P=NP
14.5 CIRCUITSAT is a “hardest” NP problem
14.6 NP-completeness is widespread
14.7 Proof techniques for NP-completeness
14.8 The good news and bad news about NP-completeness
Part III: ORIGINS AND APPLICATIONS
15 THE ORIGINAL TURING MACHINE
15.1 Turing’s definition of a “computing machine”
15.2 Machines can compute what humans can compute
15.3 The Church–Turing thesis: A law of nature?
16 YOU CAN’T PROVE EVERYTHING THAT’S TRUE
16.1 Mechanical proofs
16.2 Arithmetic as a logical system
16.3 The undecidability of mathematics
16.4 The incompleteness of mathematics
16.5 What have we learned and why did we learn it?
17 KARP’S 21 PROBLEMS
17.1 Karp’s overview
17.2 Karp’s definition of NP-completeness
17.3 The list of 21 NP-complete problems
17.4 Reductions between the 21 NP-complete problems
17.5 The rest of the paper: NP-hardness and more
18 CONCLUSION: WHAT WILL BE COMPUTED?
18.1 The big ideas about what can be computed
Bibliography
· · · · · · (收起)