Computation and its Limits
1st Edition
Published on 15. March 2012
246 pages
978-0-19-162700-2 (ISBN)
Description
Although we are entirely unaware of it, computation is central to all aspects of our existences. Every day we solve, or try to solve, a myriad of problems, from the utterly trivial to the bafflingly complex. This book explains why it is possible to do computation and what the ultimate limits of it are, as understood by modern science.
More details
Other editions
Additional editions
Paul Cockshott | Lewis M. Mackenzie | Gregory Michaelson
Computation and its Limits
Book
03/2012
1st Edition
Oxford University Press
€110.18
Shipment within 15-20 days
Content
- Cover
- 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 p-Calculus
- 8.6 $-Calculus
- 8.7 Conclusions
- Bibliography
- Index
- A
- B
- C
- D
- E
- F
- G
- H
- I
- J
- K
- L
- M
- N
- O
- P
- Q
- R
- S
- T
- U
- V
- W
- Y
- Z
