Computation and its Limits by Cockshott, Paul -- Read -- Imperial Library of Trantor

Index

Cover Page Title Page Copyright Page Contents 1 Introduction

1.1 Overview 1.2 Summary 1.3 Acknowledgements

2 What is Computation?

2.1 The Apparent Mystery of Maths 2.2 Counting Sheep 2.3 Counting Materialised in our own Bodily Movements 2.4 From ‘aides-memoire’ to the First Digital Calculating Devices

3 Mechanical Computers and their Limits

3.1 Antikythera 3.2 Late Mechanical Computers 3.3 Analogue Mechanical Multiply/Accumulate 3.4 Mechanizing the Abacus

4 Logical Limits to Computing

4.1 Introduction 4.2 Propositional logic 4.3 Set theory 4.4 Predicate logic 4.5 Recursion 4.6 Peano Arithmetic 4.7 Paradoxes 4.8 Arithmetizing Mathematics and Incompleteness 4.9 Infinities 4.10 Real Numbers and Cantor Diagonalization 4.11 Turing Machines 4.12 Universal TM and Undecidability 4.13 Computational Procedures 4.14 The Church–Turing Thesis 4.15 Machines, Programs, and Expressions

5 Heat, Information, and Geometry

5.1 The Triumph of Digital Computation 5.2 Analogue Computing with real Numbers 5.3 What Memories are made of 5.4 Power Consumption as a Limit 5.5 Entropy 5.6 Shannon’s Information Theory 5.7 Landauer’s limit 5.8 Non-entropic Computation 5.9 Interconnection

6 Quantum Computers

6.1 Foundations of Quantum Theory 6.2 The Quantum Rules 6.3 Qubits 6.4 Entanglement and Quantum Registers 6.5 Quantum Computers 6.6 Quantum Algorithms 6.7 Building a Quantum Computer 6.8 Physical Limits to real Number Representations 6.9 Error rates in Classical and Quantum Gates

7 Beyond the Logical limits of Computing?

7.1 Introduction 7.2 Oracles, Complexity, and Tractability 7.3 Beyond the Turing Machine? 7.4 Numberology 7.5 What is real about the Reals? 7.6 Real Measurement 7.7 Back to Turing 7.8 Reservations about Cantor

8 Hypercomputing Proposals

8.1 Infinite Turing Machines 8.2 Infinitely Precise Analogue Computers 8.3 Wegner and Eberbach’s Super-Turing Computers 8.4 Interaction Machines 8.5 π-Calculus 8.6 $-Calculus 8.7 Conclusions

Bibliography Index Footnote

Chapter 1 Chapter 3 Chapter 4 Chapter 5 Chapter 6