Book:A.K. Dewdney/The New Turing Omnibus: Sixty-Six Excursions in Computer Science

From ProofWiki
Jump to navigation Jump to search

A.K. Dewdney: The (New) Turing Omnibus: Sixty-Six Excursions in Computer Science

Published $1993$, W.H. Freeman

ISBN 0-8050-7166-0.


Subject Matter


Contents

Preface
Icons
$1$ ALGORITHMS Cooking Up Programs
$2$ FINITE AUTOMATA The Black Box
$3$ SYSTEMS OF LOGIC Boolean Bases
$4$ SIMULATION The Monte Carlo Method
$5$ GÖDEL'S THEOREM Limits on Logic
$6$ GAME TREES The Minimax Method
$7$ THE CHOMSKY HIERARCHY Four Computers
$8$ RANDOM NUMBERS The Chaitin-Kolmogoroff Theory
$9$ MATHEMATICAL RESEARCH The Mandelbrot Set
$10$ PROGRAM CORRECTNESS Ultimate Debugging
$11$ SEARCH TREES Traversal and Maintenance
$12$ ERROR-CORRECTING CODES Pictures from Space
$13$ BOOLEAN LOGIC Expressions and Circuits
$14$ REGULAR LANGUAGES Pumping Words
$15$ TIME AND SPACE COMPLEXITY The Big-O Notation
$16$ GENETIC ALGORITHMS Solutions That Evolve
$17$ THE RANDOM ACCESS MACHINE An Abstract Computer
$18$ SPLINE CURVES Smooth Interpolation
$19$ COMPUTER VISION Polyhedral Scenes
$20$ KARNAUGH MAPS Circuit Minimization
$21$ THE NEWTON-RAPHSON METHOD Finding Roots
$22$ MINIMUM SPANNING TREES A Fast Algorithm
$23$ GENERATIVE GRAMMARS Lindenmayer Systems
$24$ RECURSION The Sierpinski Curve
$25$ FAST MULTIPLICATION Divide and Conquer
$26$ NONDETERMINISM Automata That Guess Correctly
$27$ PERCEPTRONS A Lack of Vision
$28$ ENCODERS AND MULTIPLEXERS Manipulating Memory
$29$ CAT SCANNING Cross-Sectional X-Rays
$30$ THE PARTITION PROBLEM A Pseudo-fast Algorithm
$31$ TURING MACHINES The Simplest Computers
$32$ THE FAST FOURIER TRANSFORM Redistributing Images
$33$ ANALOG COMPUTATION Spaghetti Computers
$34$ SATISFIABILITY A Central Problem
$35$ SEQUENTIAL SORTING A Lower Bound on Speed
$36$ NEURAL NETWORKS THAT LEARN Converting Coordinates
$37$ PUBLIC KEY CRYPTOGRAPHY Intractable Secrets
$38$ SEQUENTIAL CIRCUITS A Computer Memory
$39$ NONCOMPUTABLE FUNCTIONS The Busy Beaver Problem
$40$ HEAPS AND MERGES The Fastest Sorts of Sorts
$41$ NP-COMPLETENESS The Wall of Intractability
$42$ NUMBER SYSTEMS FOR COMPUTING Chinese Arithmetic
$43$ STORAGE BY HASHING The Key Is The Address
$44$ CELLULAR AUTOMATA The Game of Life
$45$ COOK'S THEOREM Nuts and Bolts
$46$ SELF-REPLICATING COMPUTERS Codd's Machine
$47$ STORING IMAGES A Cat in a Quad Tree
$48$ THE SCRAM A Simplified Computer
$49$ SHANNON'S THEORY The Elusive Codes
$50$ DETECTING PRIMES An Algorithm that Almost Always Works
$51$ UNIVERSAL TURING MACHINES Computers as Programs
$52$ TEXT COMPRESSION Huffmann Coding
$53$ DISK OPERATING SYSTEMS Bootstrapping the Computer
$54$ NP-COMPLETE PROBLEMS The Tree of Intractability
$55$ ITERATION AND RECURSION The Towers of Hanoi
$56$ VLSI COMPUTERS Circuits in Silicon
$57$ LINEAR PROGRAMMING The Simplex Method
$58$ PREDICATE CALCULUS The Resolution Method
$59$ THE HALTING PROBLEM The Uncomputable
$60$ COMPUTER VIRUSES A Software Invasion
$61$ SEARCHING STRINGS The Boyer-Moore Algorithm
$62$ PARALLEL COMPUTING Processors with Connections
$63$ THE WORD PROBLEM Dictionaries as Programs
$64$ LOGIC PROGRAMMING Prologue to Expertise
$65$ RELATIONAL DATA BASES Do-It-Yourself Queries
$66$ CHURCH'S THESIS All Computers Are Created Equal
Index