“mcs”一2018/6/6一13：43一page iv一#4 公 Contents 5 Induction 137 5.1 Ordinary Induction 137 5.2 Strong Induction 146 5.3 Strong Induction vs.Induction vs.Well Ordering 153 6 State Machines 173 6.1 States and Transitions 173 6.2 The Invariant Principle 174 6.3 Partial Correctness Termination 182 6.4 The Stable Marriage Problem 187 7 Recursive Data Types 217 7.1 Recursive Definitions and Structural Induction 217 7.2 Strings of Matched Brackets 221 7.3 Recursive Functions on Nonnegative Integers 225 7.4 Arithmetic Expressions 227 7.5 Games as a Recursive Data Type 232 7.6 Search Trees 238 7.7 Induction in Computer Science 257 8 Infinite Sets 295 8.1 Infinite Cardinality 296 8.2 The Halting Problem 305 8.3 The Logic of Sets 309 8.4 Does All This Really Work?314 II Structures Introduction 339 9 Number Theory 341 9.1 Divisibility 341 9.2 The Greatest Common Divisor 346 9.3 Prime Mysteries 353 9.4 The Fundamental Theorem of Arithmetic 356 9.5 Alan Turing 358 9.6 Modular Arithmetic 362 9.7 Remainder Arithmetic 364 9.8 Turing's Code (Version 2.0)367 9.9 Multiplicative Inverses and Cancelling 369 9.10 Euler's Theorem 373“mcs” — 2018/6/6 — 13:43 — page iv — #4 Contentsiv 5 Induction 137 5.1 Ordinary Induction 137 5.2 Strong Induction 146 5.3 Strong Induction vs. Induction vs. Well Ordering 153 6 State Machines 173 6.1 States and Transitions 173 6.2 The Invariant Principle 174 6.3 Partial Correctness & Termination 182 6.4 The Stable Marriage Problem 187 7 Recursive Data Types 217 7.1 Recursive Definitions and Structural Induction 217 7.2 Strings of Matched Brackets 221 7.3 Recursive Functions on Nonnegative Integers 225 7.4 Arithmetic Expressions 227 7.5 Games as a Recursive Data Type 232 7.6 Search Trees 238 7.7 Induction in Computer Science 257 8 Infinite Sets 295 8.1 Infinite Cardinality 296 8.2 The Halting Problem 305 8.3 The Logic of Sets 309 8.4 Does All This Really Work? 314 II Structures Introduction 339 9 Number Theory 341 9.1 Divisibility 341 9.2 The Greatest Common Divisor 346 9.3 Prime Mysteries 353 9.4 The Fundamental Theorem of Arithmetic 356 9.5 Alan Turing 358 9.6 Modular Arithmetic 362 9.7 Remainder Arithmetic 364 9.8 Turing’s Code (Version 2.0) 367 9.9 Multiplicative Inverses and Cancelling 369 9.10 Euler’s Theorem 373