Paperback
-
PICK UP IN STORECheck Availability at Nearby Stores
Available within 2 business hours
Related collections and offers
Overview
In 1936, when he was just 24 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 for the general reader, beginning with its foundations and systematically building to its 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.
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 3 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: | 589,439 |
| Product dimensions: | 5.30(w) x 7.90(h) x 0.40(d) |
| Age Range: | 18 Years |
About the Author
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
This is a delightful introduction for the lay reader to the ideas surrounding Alan Turing's great paper of 1936.
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.
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.
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 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 WorldThis 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, MITOver 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 UsThe 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 OntarioOver 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.