Computation and its limits / Paul Cockshott, Lewis M. Mackenzie, Greg Michaelson.

Format:

Book

Author/Creator:

Cockshott, Paul.

Contributor:

Mackenzie, L. M.

Michaelson, Greg.

Language:

English

Subjects (All):

Mathematics--Data processing.

Physical Description:

1 online resource (246 p.)

Edition:

1st ed.

Place of Publication:

Oxford : Oxford University Press, 2012.

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 of logic constrain what we can compute. In the process they examine formal computability, the thermodynamics of computation and the promise of quantum computing.

Contents:

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 &amp

#960

-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.

Notes:

Includes bibliographical references and index.

Description based on metadata supplied by the publisher and other sources.

Description based on publisher supplied metadata and other sources.

ISBN:

0-19-162700-3

0-19-162749-6

9786613624604

1-280-59477-2

OCLC:

761379949