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

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

Published $\text {1993}$, W.H. Freeman

ISBN 0-8050-7166-0

Subject Matter

• Computer Science

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