Turing's vision : the birth of computer science / Chris Bernhardt.

Format:

Book

Author/Creator:

Bernhardt, Chris, author.

Language:

English

Subjects (All):

Turing, Alan, 1912-1954.

Turing, Alan.

Computer engineering--Great Britain--History.

Computer engineering.

Mathematicians--Great Britain--Biography.

Mathematicians.

Computer algorithms.

History.

Great Britain.

Computer algorithms--History.

Genre:

Biographies.

History.

Physical Description:

xvii, 189 pages : illustrations ; 21 cm

Place of Publication:

Cambridge, Massachusetts ; London, England : The MIT Press, [2016]

Summary:

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. He 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. 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. Book jacket.

Contents:

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.

Notes:

Includes bibliographical references and index.

ISBN:

9780262034548

0262034549

OCLC:

928023848