What Can Be Computed?

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.

"The concept is excellent, and it fills an important gap in the available textbooks on computation theory."---Kitty Meeks, London Mathematical Society

• AcknowledgmentsPreface for instructorsThe inspiration of GEBWhich “theory” course are we talking about?The features that might make this book appealingWhat’s in and what’s outPossible courses based on this bookComputer science as a liberal artOVERVIEW1 INTRODUCTION: WHAT CAN AND CANNOT BE COMPUTED?1.1 Tractable problems1.2 Intractable problems1.3 Uncomputable problems1.4 A more detailed overview of the bookOverview of part I: Computability theoryOverview of part II: Complexity theoryOverview of part III: Origins and applications1.5 Prerequisites for understanding this book1.6 The goals of the bookThe fundamental goal: What can be computed?Secondary goal 1: A practical approachSecondary goal 2: Some historical insight1.7 Why study the theory of computation?Reason 1: The theory of computation is usefulReason 2: The theory of computation is beautiful and importantExercisesPart I: COMPUTABILITY THEORY2 WHAT IS A COMPUTER PROGRAM?2.1 Some Python program basicsEditing and rerunning a Python programRunning a Python program on input from a fileRunning more complex experiments on Python programs2.2 SISO Python programsPrograms that call other functions and programs2.3 ASCII characters and multiline strings2.4 Some problematic programs2.5 Formal definition of Python program2.6 Decision programs and equivalent programs2.7 Real-world programs versus SISO Python programsExercises3 SOME IMPOSSIBLE PYTHON PROGRAMS3.1 Proof by contradiction3.2 Programs that analyze other programsPrograms that analyze themselves3.3 The program yesOnString.py3.4 The program yesOnSelf.py3.5 The program notYesOnSelf.py3.6 yesOnString.py can’t exist eitherA compact proof that yesOnString.py can’t exist3.7 Perfect bug-finding programs are impossible3.8 We can still find bugs, but we can’t do it perfectlyExercises4 WHAT IS A COMPUTATIONAL PROBLEM?4.1 Graphs, alphabets, strings, and languagesGraphsTrees and rooted treesAlphabetsStringsLanguages4.2 Defining computational problemsPositive and negative instancesNotation for computational problems4.3 Categories of computational problemsSearch problemsOptimization problemsThreshold problemsFunction problemsDecision problemsConverting between general and decision problemsComplement of a decision problemComputational problems with two input strings4.4 The formal definition of “solving” a problemComputable functions4.5 Recognizing and deciding languagesRecognizable languagesRecursive and recursively enumerable languagesExercises5 TURING MACHINES: THE SIMPLEST COMPUTERS5.1 Definition of a Turing machineHalting and loopingAccepters and transducersAbbreviated notation for state diagramsCreating your own Turing machines5.2 Some nontrivial Turing machinesThe moreCsThanGs machineThe countCs machineImportant lessons from the countCs example5.3 From single-tape Turing machines to multi-tape Turing machinesTwo-tape, single-head Turing machinesTwo-way infinite tapesMulti-tape, single-head Turing machinesTwo-tape, two-head Turing machines5.4 From multi-tape Turing machines to Python programs and beyondMulti-tape Turing machine → random-access Turing machineRandom-access Turing machine → real computerModern computer → Python program5.5 Going back the other way: Simulating a Turing machine with PythonA serious caveat: Memory limitations and other technicalities5.6 Classical computers can simulate quantum computers5.7 All known computers are Turing equivalentExercises6 UNIVERSAL COMPUTER PROGRAMS: PROGRAMS THAT CAN DO ANYTHING6.1 Universal Python programs6.2 Universal Turing machines6.3 Universal computation in the real world6.4 Programs that alter other programsIgnoring the input and performing a fixed calculation instead6.5 Problems that are undecidable but recognizableExercises7 REDUCTIONS: HOW TO PROVE A PROBLEM IS HARD7.1 A reduction for easiness7.2 A reduction for hardness7.3 Formal definition of Turing reductionWhy “Turing” reduction?Oracle programsWhy is ≤T used to denote a Turing reduction?Beware the true meaning of “reduction”7.4 Properties of Turing reductions7.5 An abundance of uncomputable problemsThe variants of YESONSTRINGThe halting problem and its variantsUncomputable problems that aren’t decision problems7.6 Even more uncomputable problemsThe computational problem COMPUTESFRice’s theorem7.7 Uncomputable problems that aren’t about programs7.8 Not every question about programs is uncomputable7.9 Proof techniques for uncomputabilityTechnique 1: The reduction recipeTechnique 2: Reduction with explicit Python programsTechnique 3: Apply Rice’s theoremExercises8 NONDETERMINISM: MAGIC OR REALITY?8.1 Nondeterministic Python programs8.2 Nondeterministic programs for nondecision problems8.3 Computation trees8.4 Nondeterminism doesn’t change what is computable8.5 Nondeterministic Turing machines8.6 Formal definition of nondeterministic Turing machines8.7 Models of nondeterminism8.8 Unrecognizable problems8.9 Why study nondeterminism?Exercises9 FINITE AUTOMATA: COMPUTING WITH LIMITED RESOURCES9.1 Deterministic finite automata9.2 Nondeterministic finite automataState diagrams for nfasFormal definition of an nfaHow does an nfa accept a string?Sometimes nfas make things easier9.3 Equivalence of nfas and dfasNondeterminism can affect computability: The example of pdasPracticality of converted nfasMinimizing the size of dfas9.4 Regular expressionsPure regular expressionsStandard regular expressionsConverting between regexes and finite automata9.5 Some languages aren’t regularThe nonregular language GnTnThe key difference between Turing machines and finite automata9.6 Many more nonregular languagesThe pumping lemma9.7 Combining regular languagesExercisesPart II: COMPUTATIONAL COMPLEXITY THEORY10 COMPLEXITY THEORY: WHEN EFFICIENCY DOES MATTER10.1 Complexity theory uses asymptotic running times10.2 Big-O notationDominant terms of functionsA practical definition of big-O notationSuperpolynomial and subexponentialOther asymptotic notationComposition of polynomials is polynomialCounting things with big-O10.3 The running time of a programRunning time of a Turing machineRunning time of a Python programThe lack of rigor in Python running times10.4 Fundamentals of determining time complexityA crucial distinction: The length of the input versus the numerical value of the inputThe complexity of arithmetic operationsBeware of constant-time arithmetic operationsThe complexity of factoringThe importance of the hardness of factoringThe complexity of sorting10.5 For complexity, the computational model does matterSimulation costs for common computational modelsMulti-tape simulation has quadratic costRandom-access simulation has cubic costUniversal simulation has logarithmic costReal computers cost only a constant factorPython programs cost the same as real computersPython programs can simulate random-access Turing machines efficientlyQuantum simulation may have exponential costAll classical computational models differ by only polynomial factorsOur standard computational model: Python programs10.6 Complexity classesExercises11 Poly AND Expo: THE TWO MOST FUNDAMENTAL COMPLEXITY CLASSES11.1 Definitions of Poly and ExpoPoly and Expo compared to P, Exp, and FP11.2 Poly is a subset of Expo11.3 A first look at the boundary between Poly and ExpoALL3SETS and ALLSUBSETSTraveling salespeople and shortest pathsMultiplying and factoringBack to the boundary between Poly and ExpoPrimality testing is in Poly11.4 Poly and Expo don’t care about the computational model11.5 HALTEx: A decision problem in Expo but not Poly11.6 Other problems that are outside Poly11.7 Unreasonable encodings of the input affect complexity11.8 Why study Poly, really?Exercises12 PolyCheck AND NPoly: HARD PROBLEMS THAT ARE EASY TO VERIFY12.1 VerifiersWhy “unsure”?12.2 Polytime verifiersBounding the length of proposed solutions and hintsVerifying negative instances in exponential timeSolving arbitrary instances in exponential time12.3 The complexity class PolyCheckSome PolyCheck examples: PACKING,SUBSETSUM, and PARTITIONThe haystack analogy for PolyCheck12.4 The complexity class NPoly12.5 PolyCheck and NPoly are identicalEvery PolyCheck problem is in NPolyEvery NPoly problem is in PolyCheck12.6 The PolyCheck/NPoly sandwich12.7 Nondeterminism does seem to change what is computable efficiently12.8 The fine print about NPolyAn alternative definition of NPolyNPoly compared to NP and FNPExercises13 POLYNOMIAL-TIME MAPPING REDUCTIONS: PROVING X IS AS EASY AS Y13.1 Definition of polytime mapping reductionsPolyreducing to nondecision problems13.2 The meaning of polynomial-time mapping reductions13.3 Proof techniques for polyreductions13.4 Examples of polyreductions using Hamilton cyclesA polyreduction from UHC to DHCA polyreduction from DHC to UHC13.5 Three satisfiability problems: CIRCUITSAT, SAT, and 3-SATWhy do we study satisfiability problems?CIRCUITSATSATConjunctive normal formASCII representation of Boolean formulas3-SAT13.6 Polyreductions between CIRCUITSAT, SAT, and 3-SATThe Tseytin transformation13.7 Polyequivalence and its consequencesExercises14 NP-COMPLETENESS: MOST HARD PROBLEMS ARE EQUALLY HARD14.1 P versus NP14.2 NP-completenessReformulations of P versus NP using NP-completeness14.3 NP-hardness14.4 Consequences of P=NP14.5 CIRCUITSAT is a “hardest” NP problem14.6 NP-completeness is widespread14.7 Proof techniques for NP-completeness14.8 The good news and bad news about NP-completenessProblems in NPoly but probably not NP-hardSome problems that are in PSome NP-hard problems can be approximated efficientlySome NP-hard problems can be solved efficiently for real-world inputsSome NP-hard problems can be solved in pseudo-polynomial timeExercisesPart III: ORIGINS AND APPLICATIONS15 THE ORIGINAL TURING MACHINE15.1 Turing’s definition of a “computing machine”15.2 Machines can compute what humans can compute15.3 The Church–Turing thesis: A law of nature?The equivalence of digital computersChurch’s thesis: The equivalence of computer programs and algorithmsTuring’s thesis: The equivalence of computer programs and human brainsChurch–Turing thesis: The equivalence of all computational processesExercises16 YOU CAN’T PROVE EVERYTHING THAT’S TRUEThe history of computer proofs16.1 Mechanical proofsSemantics and truthConsistency and completenessDecidability of logical systems16.2 Arithmetic as a logical systemConverting the halting problem to a statement about integersRecognizing provable statements about integersThe consistency of Peano arithmetic16.3 The undecidability of mathematics16.4 The incompleteness of mathematics16.5 What have we learned and why did we learn it?Exercises17 KARP’S 21 PROBLEMS17.1 Karp’s overview17.2 Karp’s definition of NP-completeness17.3 The list of 21 NP-complete problems17.4 Reductions between the 21 NP-complete problemsPolyreducing SAT to CLIQUEPolyreducing CLIQUE to NODE COVERPolyreducing DHC to UHCPolyreducing SAT to 3-SATPolyreducing KNAPSACK to PARTITION17.5 The rest of the paper: NP-hardness and moreExercises18 CONCLUSION: WHAT WILL BE COMPUTED?18.1 The big ideas about what can be computedBibliographyIndex