Computation and its Limits

by Cockshott, Paul; Mackenzie, Lewis M; Michaelson, Gregory

• ISBN13: 9780199640324
• ISBN10: 0199640327
• Format: Hardcover
• Copyright: 2012-04-07
• Publisher: Oxford University Press

Summary

Computation and its Limits is an innovative cross-disciplinary investigation of the relationship between computing and physical reality. It begins by exploring the mystery of why mathematics is so effective in science and seeks to explain this in terms of the modelling of one part of physical reality by another. Going from the origins of counting to the most blue-skies proposals for novel methods of computation, the authors investigate the extent to which the laws of nature and oflogic constrain what we can compute. In the process they examine formal computability, the thermodynamics of computation and the promise of quantum computing.

Table of Contents

Introduction	p. 1
Overview	p. 1
Summary	p. 4
Acknowledgements	p. 5
What is computation?	p. 6
The apparent mystery of maths	p. 6
Counting sheep	p. 11
Counting materialised in our own bodily movements	p. 16
From 'aides-memoire' to the first digital calculating devices	p. 23
Mechanical computers and their limits	p. 28
Antikythera	p. 28
Late mechanical computers	p. 35
Analogue mechanical multiply/accumulate	p. 39
Mechanizing the abacus	p. 42
Logical limits to computing	p. 47
Introduction	p. 47
Propositional logic	p. 47
Set theory	p. 51
Predicate logic	p. 52
Recursion	p. 55
Peano arithmetic	p. 55
Paradoxes	p. 58
Arithmetizing mathematics and incompleteness	p. 61
Infinities	p. 64
Real numbers and Cantor diagonahzation	p. 66
Turing machines	p. 67
Universal TM and undecidability	p. 71
Computational procedures	p. 74
The Church-Turing thesis	p. 78
Machines, programs, and expressions	p. 79
Heat, information, and geometry	p. 83
The triumph of digital computation	p. 83
Analogue computing with real numbers	p. 84
What memories are made of	p. 86
Power consumption as a limit	p. 91
Entropy	p. 95
Shannon's information theory	p. 111
Landauer's limit	p. 114
Non-entropic computation	p. 117
Interconnection	p. 122
Quantum computers	p. 128
Foundations of quantum theory	p. 128
The quantum rules	p. 136
Qubits	p. 142
Entanglement and quantum registers	p. 146
Quantum computers	p. 153
Quantum algorithms	p. 155
Building a quantum computer	p. 157
Physical limits to real number representations	p. 167
Error rates in classical and quantum gates	p. 171
Beyond the logical limits of computing?	p. 173
Introduction	p. 173
Oracles, complexity, and tractability	p. 174
Beyond the Turing Machine?	p. 176
Numberology	p. 177
What is real about the reals?	p. 180
Real measurement	p. 181
Back to Turing	p. 184
Reservations about Cantor	p. 185
Hypercomputing proposals	p. 187
Infinite Turing Machines	p. 187
Infinitely precise analogue computers	p. 190
Wegner and Eberbach's super-Turing computers	p. 201
Interaction Machines	p. 202
¿-Calculus	p. 206
$-Calculus	p. 211
Conclusions	p. 214
Bibliography	p. 216
Index	p. 226
Table of Contents provided by Ingram. All Rights Reserved.