Turing's Vision: The Birth of Computer Science

Turing's Vision: The Birth of Computer Science

by Chris Bernhardt

Paperback

$17.96 $19.95 Save 10% Current price is $17.96, Original price is $19.95. You Save 10%.
View All Available Formats & Editions
Choose Expedited Shipping at checkout for guaranteed delivery by Wednesday, August 28

Overview

Turing's fascinating and remarkable theory, which now forms the basis of computer science, explained for the general reader.

In 1936, when he was just twenty-four years old, Alan Turing wrote a remarkable paper in which he outlined the theory of computation, laying out the ideas that underlie all modern computers. This groundbreaking and powerful theory now forms the basis of computer science. In Turing's Vision , Chris Bernhardt explains the theory, Turing's most important contribution, for the general reader. Bernhardt argues that the strength of Turing's theory is its simplicity, and that, explained in a straightforward manner, it is eminently understandable by the nonspecialist. As Marvin Minsky writes, “The sheer simplicity of the theory's foundation and extraordinary short path from this foundation to its logical and surprising conclusions give the theory a mathematical beauty that alone guarantees it a permanent place in computer theory. ” Bernhardt begins with the foundation and systematically builds to the surprising conclusions. He also views Turing's theory in the context of mathematical history, other views of computation (including those of Alonzo Church), Turing's later work, and the birth of the modern computer.

In the paper, “On Computable Numbers, with an Application to the Entscheidungsproblem ,” Turing thinks carefully about how humans perform computation, breaking it down into a sequence of steps, and then constructs theoretical machines capable of performing each step. Turing wanted to show that there were problems that were beyond any computer's ability to solve; in particular, he wanted to find a decision problem that he could prove was undecidable. To explain Turing's ideas, Bernhardt examines three well-known decision problems to explore the concept of undecidability; investigates theoretical computing machines, including Turing machines; explains universal machines; and proves that certain problems are undecidable, including Turing's problem concerning computable numbers.

Product Details

ISBN-13: 9780262533515
Publisher: MIT Press
Publication date: 04/21/2017
Series: The MIT Press
Pages: 208
Sales rank: 267,506
Product dimensions: 5.30(w) x 7.90(h) x 0.40(d)
Age Range: 18 Years

About the Author

Chris Bernhardt is Professor of Mathematics at Fairfield University and the author of Turing's Vision: The Birth of Computer Science (MIT Press).

Table of Contents

Acknowledgments ix

Introduction xi

1 Background 1

Mathematical Certainty 2

Boole's Logic 4

Mathematical Logic 5

Securing the Foundations of Mathematics 7

Hilbert's Approach 8

Gödel's Results 10

Turing's Results 11

2 Some Undecidable Decision Problems 15

Emil Post 16

Post's Correspondence Problem 17

Hilbert's Tenth Problem 22

The Halting Problem 24

Back to Turing at Cambridge 24

3 Finite Automata 25

Introduction 25

Finite Automata 27

Our First Machine 27

Alphabets and Languages 29

Finite Automata and Answering Questions 31

Omitting Traps from Diagrams 33

Some Basic Facts 35

Regular Expressions 37

Limitations of Finite Automata 41

Tapes and Configurations 43

Connection to the Correspondence Problem 44

4 Turing Machines 47

Examples of Turing Machines 52

Computable Functions and Calculations 59

Church-Turing Thesis 61

Computational Power 63

Machines That Don't Halt 67

5 Other Systems for Computation 69

The Lambda Calculus 72

Tag Systems 79

One-Dimensional Cellular Automata 82

6 Encodings and the Universal Machine 87

A Method of Encoding Finite Automata 88

Universal Machines 91

Construction of Universal Machines 93

Modern Computers Are Universal Machines 95

Von Neumann Architecture 97

Random Access Machines 98

RAMs Can Be Emulated by Turing Machines 101

Other Universal Machines 103

What Happens When We Input (M) into M? 104

7 Undecidable Problems 107

Proof by Contradiction 108

Russell's Barber 111

Finite Automata That Do Not Accept Their Encodings 113

Turing Machines That Do Not Accept Their Encodings 114

Does a Turing Machine Diverge on Its Encoding? Is Undecidable 116

The Acceptance, Hafting, and Blank Tape Problems 117

An Uncomputable Function 119

Turing's Approach 120

8 Cantor's Diagonalization Arguments 123

Georg Cantor 1845-1918 123

Cardinality 124

Subsets of the Rationals That Have the Same Cardinality 126

Hilbert's Hotel 129

Subtraction Is Not Well-Defined 131

General Diagonal Argument 131

The Cardinality of the Real Numbers 135

The Diagonal Argument 138

The Continuum Hypothesis 139

The Cardinality of Computations 140

Computable Numbers 141

A Non-Computable Number 142

There Is a Countable Number of Computable Numbers 143

Computable Numbers Are Not Effectively Enumerable 143

9 Turing's Legacy 147

Turing at Princeton 148

Second World War 150

Development of Computers in the 1940s 153

The Turing Test 157

Downfall 159

Apology and Pardon 161

Further Reading 163

Notes 167

Bibliography 183

Index 187

What People are Saying About This

Scott Aaronson

This is a delightful introduction for the lay reader to the ideas surrounding Alan Turing's great paper of 1936.

Ian Stewart

A fascinating account of Alan Turing's epic research paper, which kicked off the entire computer revolution. I'm particularly impressed by the amount of detail the author includes while keeping everything simple, transparent, and a pleasure to read.

From the Publisher

A fascinating account of Alan Turing's epic research paper, which kicked off the entire computer revolution. I'm particularly impressed by the amount of detail the author includes while keeping everything simple, transparent, and a pleasure to read.

Ian Stewart , author of In Pursuit of the Unknown: 17 Equations That Changed the World

This is a delightful introduction for the lay reader to the ideas surrounding Alan Turing's great paper of 1936.

Scott Aaronson , Associate Professor of Electrical Engineering and Computer Science, MIT

Over the past several decades, Alan Turing, known as the father of computer science, has become an intellectual and cultural icon. Chris Bernhardt has written a very clear and accessible book that explains Turing's work, showing how his ideas have developed into some of the most important ideas in computer science today.

Noson S. Yanofsky , author of The Outer Limits of Reason: What Science, Mathematics, and Logic Cannot Tell Us

The dazzling array of computer applications, from desktop to cell phone, has obscured the play of ideas that first set our modern era in motion. In this account, Bernhardt reveals the crucial contribution to these developments made by Alan Turing and other early computer scientists. A marvelous book.

A. K. Dewdney , Professor Emeritus, Department of Computer Science, University of Western Ontario

Endorsement

The dazzling array of computer applications, from desktop to cell phone, has obscured the play of ideas that first set our modern era in motion. In this account, Bernhardt reveals the crucial contribution to these developments made by Alan Turing and other early computer scientists. A marvelous book.

A. K. Dewdney, Professor Emeritus, Department of Computer Science, University of Western Ontario

A. K. Dewdney

The dazzling array of computer applications, from desktop to cell phone, has obscured the play of ideas that first set our modern era in motion. In this account, Bernhardt reveals the crucial contribution to these developments made by Alan Turing and other early computer scientists. A marvelous book.

Noson S. Yanofsky

Over the past several decades, Alan Turing, known as the father of computer science, has become an intellectual and cultural icon. Chris Bernhardt has written a very clear and accessible book that explains Turing's work, showing how his ideas have developed into some of the most important ideas in computer science today.

Customer Reviews

Most Helpful Customer Reviews

See All Customer Reviews