# The Programmer’s Guide To Theory

Great ideas explained

## Buy from: Amazon

**Computer science, specifically the theory of computation**, deserves to be better known even among non-computer scientists. The reason is simply that it is full of profound thoughts and ideas. It contains some paradoxes that reveal the limits of human knowledge. It provides ways to reason about information and randomness that are understandable without the need to resort to abstract math. This is not an academic textbook but could be the precursor to reading an academic textbook.

In **Programmer’s Guide to Theory**, you will find the fundamental ideas of computer science explained in an informal and yet informative way. The first chapter sets the scene by outlining the challenges of understanding computational theory. After this the content is divided into three parts. The first explores the question “What is Computable?” introducing the Turing Machine, the Halting Problem and Finite State Machines before going on to consider the different types of computing model that are available and the languages they produce. This part also covers the different types of numbers and of infinities which paves the way for considering the topics of Kolmogorov Complexity and randomness, the Axiom of Choice, Godel’s Incompleteness and the Lambda Calculus. Part II switches to lower-level concerns – from bits to Boolean logic covering information theory and error correction along the way. Part III dives deeper into computational complexity, considers polynomial-time versus exponential-time problems and then explores the benefits of recursion. It concludes with a discussion of NP (non-deterministic polynomial) versus P (polynomial) algorithms.

Don’t be put off by this list of unfamiliar concepts. This book sets out to lead you from one topic to the next so that the ideas are unfolded gradually. It does cover all the ideas that are fundamental to computer science, plus some that are not normally included but make things easier to understand, but does so in a very approachable, and even entertaining way.

**Paperback:**214 pages**Publisher:**I/O Press (November 24, 2019)**Language:**English**ISBN-10:**1871962439**ISBN-13:**978-1871962437

## Errata

Page 132 - should be GHz, and MHz not gHz and mHz

## Contents

**Chapter 1 **

**What Is Computer Science? **

Computable? 12

Hard or Easy? 13

Understanding Computational Theory 15

The Roadmap 15

**Part I What Is Computable?**

**Chapter 2 **

**What Is Computation? **

Turing Machines 19

Tapes and Turing Machines 20

Infinite or Simply Unlimited 23

The Church-Turing Thesis 24

Turing-Complete 25

Summary 27

**Chapter 3 **

**The Halting Problem **

The Universal Turing Machine 29

What Is Computable? The Halting Problem 30

Reduction 32

The Problem With Unbounded 33

Non-Computable Numbers 36

Summary 38

**Chapter 4 **

**Finite State Machines **

A Finite History 39

Representing Finite State Machines 40

Finite Grammars 41

Grammar and Machines 43

Regular Expressions 44

Other Grammars 45

Turing Machines 47

Turing Machines and Finite State Machines 49

Turing Thinking 50

Summary 54

**Chapter 5 **

**Practical Grammar **

Backus-Naur Form - BNF 55

Extended BNF 57

BNF in Pictures - Syntax Diagrams 58

Why Bother? 59

Generating Examples 59

Syntax Is Semantics 60

Traveling the Tree 62

A Real Arithmetic Grammar 62

Summary 63

**Chapter 6 **

**Numbers, Infinity and Computation **

Integers and Rationals 65

The Irrationals 67

The Number Hierarchy 68

Aleph-Zero and All That 70

Unbounded Versus Infinite 71

Comparing Size 72

In Search of Aleph-One 73

What Is Bigger than Aleph-Zero? 74

Finite But Unbounded “Irrationals” 76

Enumerations 76

Enumerating the Irrationals 78

Aleph-One and Beyond 79

Not Enough Programs! 80

Not Enough Formulas! 82

Transcendental and Algebraic Irrationals 83

π - the Special Transcendental 84

Summary 85

**Chapter 7 **

**Kolmogorov Complexity and Randomness **

Algorithmic Complexity 87

Kolmogorov Complexity Is Not Computable 89

Compressability 90

Random and Pseudo Random 91

Randomness and Ignorance 92

Pseudo Random 93

True Random 94

Summary 96

**Chapter 8 **

**Algorithm of Choice **

Zermelo and Set Theory 97

The Axiom of Choice 98

To Infinity and... 98

Choice and Computability 100

Non-Constructive 101

Summary 103

**Chapter 9 **

**Gödel’s Incompleteness Theorem **

The Mechanical Math Machine 106

The Failure Axioms 108

Gödel’s First Incompleteness Theorem 108

End of the Dream 111

Summary 112

**Chapter 10**

**Lambda Calculus **

What is Computable? 113

The Basic Lambda 114

Reduction 115

Reduction As Function Evaluation 116

More Than One Parameter 117

More Than One Function 118

Bound, Free and Names 118

Using Lambdas 119

The Role of Lambda In Programming 121

Summary 122

**Part II Bits, Codes and Logic **

**Chapter 11 **

**Information Theory **

Surprise, Sunrise! 126

Logs 127

Bits 129

A Two-Bit Tree 130

The Alphabet Game 131

Compression 131

Channels, Rates and Noise 132

More Information - Theory 133

Summary 134

**Chapter 12 **

**Coding Theory – Splitting the Bit **

Average Information 135

Make it Equal 137

Huffman Coding 138

Efficient Data Compression 140

Summary 142

**Chapter 13 **

**Error Correction **

Parity Error 143

Hamming Distance 144

Hypercubes 146

Error Correction 147

Real Codes 147

Summary 149

**Chapter 14**

**Boolean Logic **

Who was George Boole? 151

Boolean Logic 152

Truth Tables 152

Practical Truth Tables 153

From Truth Tables to Electronic Circuits 154

Logic in Hardware 155

Binary Arithmetic 156

Sequential Logic 158

De Morgan's Laws 159

The Universal Gate 160

Logic, Finite State Machines and Computers 162

Summary 163

**Part III Computational Complexity**

**Chapter 15 **

**How Hard Can It Be? **

Orders 167

Problems and Instances 169

Polynomial Versus Exponential Time 170

A Long Wait 171

Where do the Big Os Come From? 172

Finding the Best Algorithm 174

How Fast can you Multiply? 174

Prime Testing 175

Summary 178

**Chapter 16 **

**Recursion **

Ways of Repeating Things 180

Self-Reference 181

Functions as Objects 182

Conditional recursion 183

Forward and Backward Recursion 185

What Use is Recursion? 186

A Case for Recursion -The Binary Tree 187

Nested Loops 188

The Paradox of Self-Reference 190

Summary 191

**Chapter 17 **

**NP Versus P Algorithms **

Functions and Decision Problems 193

Non-Deterministic Polynomial Problems 194

Co-NP 195

Function Problems 196

The Hamiltonian Problem 197

Boolean Satisfiability 198

NP-Complete and Reduction 199

Proof That SAT Is NP-Complete 199

NP-Hard 201

What if P = NP? 202

Summary 204

### About the Author

Mike James is editor of I-Programmer.info, an online magazine written by programmers for programmers. He has a BSc in Physics, an MSc in Mathematics and a PhD in Computer Science. As an author he has published dozens of books, the latest being The Programmers Guide to Kotlin, Android Programming in Kotlin and Android Programming in Java.