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.
