Updated and expanded, The Turing Omnibus offers 66 concise, brilliantly written articles on the major points of interest in computer science theory, technology, and applications. New for this tour: updated information on algorithms, detecting primes, noncomputable functions, and self-replicating computers--plus completely new sections on the Mandelbrot set, genetic algorithms, the Newton-Raphson Method, neural networks that learn, DOS systems for personal computers, and computer viruses.

Icons

ALGORITHMS Cooking Up Programs

FINITE AUTOMATA The Black Box

SYSTEMS OF LOGIC Boolean Bases

SIMULATION The Monte Carlo Method

GÖDEL'S THEOREM Limits on Logic

GAME TRESS The Minimax Method

THE COMSKY HIERARCHY Four Computers

RANDOM NUMBERS The Chaitin-Kolmogoroff Theory

MATHEMATICAL RESEARCH The Mandelbrot Set

PROGRAM CORRECTNESS Ultimate Debugging

SEARCH TRESS Traversal and Maintenance

ERROR-CORRECTING CODE Pictures from Space

BOOLEAN LOGIC Expressions and Circuits

REGULAR LANGUAGE Pumping Words

TIME AND SPACE COMPLEXITY The Big-0 Notation

GENETIC ALGORITHMS Solutions That Evolve

THE RANDOM ACCESS MACHINE An Abstract Computer

SPINAL CURVES Smooth Interpolation

COMPUTER VISION Polyhedral Scenes

KARNAUGH MAPS Circuit Minimization

THE NEWTON-RAPHSON METHOD Finding Roots

MINIMUM SPANNING TREES A Fast Algorithm

GENERATIVE GRAMMARS Lindenmayer Systems

RECURSION The Sierpinski Curve

FAST MULTIPLICATION Divide and Conquer

NONDETERMINISM Automata That Guess Correctly

PERCEPTIONS A Lack of Vision

ENCODERS AND MULTIPLEXERS Manipulating Memory

CAT SCANNING Cross-Sectional X-Rays

TIE PARTITION PROBLEM A Pseudo-fast Algorithm

TURING MACHINES The Simplest Computers

THE FAST FOURIER TRANSFORM Redistributing Images

ANALOG COMPUTATION Spaghetti Computers

SATISFIABILITY A Central Problem

SEQUENTIAL SORTING A Lower Bound on Speed

NEURAL NETWORKS THAT LEARN Converting Coordinates

PUBLIC KEY CRYPTOGRAPHY Intractable Secrets

SEQUENTIAL CIRCUITS A Computer Memory

NONCOMPUTABLE FUNCTIONS The Busy Beaver Problem

HEAPS AND MERGES The Fastest Sorts of Sorts

NP-COMPLETENESS Wall of Intractability

NUMBER SYSTEMS FOR COMPUTING Chinese Arithmetic

STORAGE BY HASHING The Key Is the Address

CELLULAR AUTOMATA The Game of Life

COOK'S THEOREM Nuts and Bolts

SELF-REPLICATING COMPUTERS Codd's Machine

STORING IMAGES A Cat in a Quad Tree

THE SCRAM A Simplified Computer

SHANNON'S THEORY The Elusive Codes

DETECTING PRIMES An Algorithm that Almost Always Works

UNIVERSAL TURING MACHINES Computers as Programs

TEXT COMPRESSION Huffman Coding

DISK OPERATING SYSTEMS Bootstrapping the Computer

NP-COMPLETE PROBLEMS The Tree of Intractability

ITERATION AND RECURSION The Towers of Hanoi

VLSI COMPUTERS Circuits in Silicon

LINEAR PROGRAMMING The Simplex Method

PREDICATE CALCULUS The Resolution Method

THE HALTING PROBLEM The Uncomputable

COMPUTER VIRUSES A Software Invasion

SEARCHING STRINGS The Boyer-Moore Algorithm

PARALLEL COMPUTING Processors with Connections

THE WORD PROBLEM Dictionaries as Programs

LOGIC PROGRAMMING Prologue to Expertise

RELATIONAL DATABASES Do-It-Yourself Queries

CHURCH'S THESIS All Computers Are Created Equal

Index