Computation and its Limits

Cover......Page 1
Contents......Page 6
1.1 Overview......Page 8
1.2 Summary......Page 11
1.3 Acknowledgements......Page 12
2.1 The apparent mystery of maths......Page 13
2.2 Counting sheep......Page 18
2.3 Counting materialised in our own bodily movements......Page 23
2.4 From ‘aides-memoire’ to the first digital calculating devices......Page 30
3.1 Antikythera......Page 35
3.2 Late mechanical computers......Page 42
3.3 Analogue mechanical multiply/accumulate......Page 46
3.4 Mechanizing the abacus......Page 49
4.2 Propositional logic......Page 54
4.3 Set theory......Page 58
4.4 Predicate logic......Page 59
4.6 Peano arithmetic......Page 62
4.7 Paradoxes......Page 65
4.8 Arithmetizing mathematics and incompleteness......Page 68
4.9 Infinities......Page 71
4.10 Real numbers and Cantor diagonalization......Page 73
4.11 Turing machines......Page 74
4.12 Universal TM and undecidability......Page 78
4.13 Computational procedures......Page 81
4.14 The Church–Turing thesis......Page 85
4.15 Machines, programs, and expressions......Page 86
5.1 The triumph of digital computation......Page 90
5.2 Analogue computing with real numbers......Page 91
5.3 What memories are made of......Page 93
5.4 Power consumption as a limit......Page 98
5.5 Entropy......Page 102
5.6 Shannon’s information theory......Page 118
5.7 Landauer’s limit......Page 121
5.8 Non-entropic computation......Page 124
5.9 Interconnection......Page 129
6.1 Foundations of quantum theory......Page 135
6.2 The quantum rules......Page 143
6.3 Qubits......Page 149
6.4 Entanglement and quantum registers......Page 153
6.5 Quantum computers......Page 160
6.6 Quantum algorithms......Page 162
6.7 Building a quantum computer......Page 164
6.8 Physical limits to real number representations......Page 174
6.9 Error rates in classical and quantum gates......Page 178
7.1 Introduction......Page 180
7.2 Oracles, complexity, and tractability......Page 181
7.3 Beyond the Turing Machine?......Page 183
7.4 Numberology......Page 184
7.5 What is real about the reals?......Page 187
7.6 Real measurement......Page 188
7.7 Back to Turing......Page 191
7.8 Reservations about Cantor......Page 192
8.1 Infinite Turing Machines......Page 194
8.2 Infinitely precise analogue computers......Page 197
8.3 Wegner and Eberbach’s super-Turing computers......Page 208
8.4 Interaction Machines......Page 209
8.5 π-Calculus......Page 213
8.6 $-Calculus......Page 218
8.7 Conclusions......Page 221
Bibliography......Page 223
A......Page 233
C......Page 234
D......Page 235
E......Page 236
G......Page 237
I......Page 238
M......Page 239
N......Page 240
P......Page 241
Q......Page 242
S......Page 243
U......Page 245
Z......Page 246