Overview
The Turing Omnibus purposely presents its sequence of 66
excursions in a rather random order. I do not intend to cover it in this
way. Below is a re-ordering of the Table of Contents by grouping the chapters into
general topics, which I will cover one at a time. I do not know yet in what order I
will cover the topics, and not all of the chapters will be required reading. But at
least this will give you an idea of what we might cover.
Algorithms and Complexity:
1. Algorithms (Cooking Up Programs) (p 1)
11. Search Trees (Traversal and Maintenance) (p 69)
15. Time and Space Complexity (The Big-O Notation) (p 96)
22. Minimum Spanning Trees (A Fast Algorithm) (p 146)
30. The Partition Problem (A Pseudo-fast Algorithm) (p 201)
35. Sequential Sorting (A Lower Bound on Speed) (p 237)
40. Heaps and Merges (The Fastest Sorts of Sorts) (p 269)
50. Detecting Primes (an Algorithm that Almost Always Works) (p 335)
NP Completeness:
34. Satisfiability (A Central Problem) (p 231)
41. NP-Completeness (The Wall of Intractability) (p 276)
45. Cook's Theorem (Nuts and Bolts) (p 301)
54. NP-Complete Problems (The Tree of Intractability)
(p 357)
Languages and Automata:
2. Finite Automata ( The Black Box) (p 8)
7. The Chomsky Hierarchy (Four Computers) (p 42)
14. Regular Languages (Pumping Words) (p 91)
23. Generative Grammars (Lindenmayer Systems) (p 152)
26. Nondeterminism (Automata That Guess Correctly) (p 174)
Computability:
17. The Random Access Machine (An Abstract Computer) (p 109)
31. Turing Machines (The Simplest Computers) (p 207)
39. Noncomputable Functions (The Busy Beaver Problem) (p 265)
51. Universal Turing Machines (Computer as Programs) (p 339)
59. The Halting Problem (The Uncomputable) (p 391)
63. The Word Problem (Dictionaries as Programs) (p 415)
66. Church's Thesis (All Computers are Created Equal) (p 434)
Logical foundations:
3. Systems of Logic (Boolean Bases) (p 14)
5. Godel's Theorem (Limits on Logic) (p 29)
58. Predicate Calculus (The Resolution Method) (p 382)
Programming:
4. Simulation (The Monte Carlo Method) (p 22)
10. Program Correctness (Ultimate Debugging) (p 63)
24. Recursion (the Sierpinski Curve) (p 159)
53. Disk Operating Systems (Bootstrapping the Computer) (p 351)
55. Iteration and Recursion (The Towers of Hanoi) (p 363)
60. Computer Viruses (A Software Invasion) (p
396)
64. Logic Programming (Prologue to Expertise) (p 420)
Digital circuits and computer architecture:
13. Boolean Logic (Expressions and Circuits) (p
82)
20. Karnaugh Maps (Circuit Minimization) (p 131)
28. Encoders and Multiplexers (Manipulating Memory) (p 188)
33. Analog Computation (Spaghetti Computers) (p 223)
38. Sequential Circuits (A Computer Memory) (p 258)
48. The Scram (A Simplified Computer) (p 321)
56. VLSI Computers (Circuits in Silicon) (p 368)
62. Parallel Computing (Processor with Connections) (p 408)
AI / Learning / Graphics / Vision:
6. Game Trees (The Minimax Method) (p 36)
9. Mathematical Research (The Mandelbrot Set) (p 56)
16. Genetic Algorithms (Solutions That Evolve) (p 103)
19. Computer Vision (Polyhedral Scenes) (p 121)
27. Perceptrons (A Lack of Vision) (p 181)
36. Neural Networks That Learn (Converting Coordinates) (p 241)
44. Cellular Automata (The Game of Life) (p 295)
46. Self-replicating Computers (Codd's Machine) (p 307)
47. Storing Images (A Cat in a Quad Tree) (p 315)
29. Cat Scanning (Cross-Sectional X-rays) (p 193)
Numerical methods:
18. Spline Curves (Smooth Interpolation) (p 116)
21. The Newton-Raphson Method (Finding Roots) (p 139)
25. Fast Multiplication (Divide and Conquer) (p 167)
32. The Fast Fourier Transform (Redistributing Images) (p 217)
57. Linear Programming (The Simplex Method) (p 374)
Information encoding / retrieval / security:
8. Random Numbers (The Chaitin-Kolmogoroff Theory) (p 49)
12. Error-Correcting Codes (Pictures from Space) (p 77)
37. Public Key Cryptography (Intractable Secrets) (p 250)
42. Number Systems for Computing (Chinese Arithmetic) (p 282)
43. Storage by Hashing (The Key is the Address) (p 288)
49. Shannon's Theory (The Elusive Codes) (p 329)
52. Text Compression (Huffman Coding) (p 345)
61. Searching Strings (The Boyer-Moore Algorithm) (p 403)
65. Relational Data Bases (Do-It-Yourself Queries) (p 427)