Computation and its Limits
Format: PDF / Kindle (mobi) / ePub
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.
it was aligned with the target, after 3.3 Analogue mechanical multiply/accumulate 39 Fig. 3.10 A Dumaresq analogue mechanical computer used in naval gunnery computations. The one illustrated is a Wind Dumaresq, which in addition to giving corrections for relative motion of the ships also provides an additional compensation term due to the wind. Image from a model by R. Brassington, with his permission. which the range rate and deﬂection normal to the line of sight could be read oﬀ the scale.
modern chip. An AMD K10, for example, has of the order of 5 × 108 gates. The power used will depend on the fraction of the gates that switch each cycle; if 10% switch each cycle, the total power consumption of the chip would be about 65 W. Clearly, the above model is very approximate. The fraction of gates switching each cycle is a guess, and we have made the simplifying assumption that gates are squares of edge the minimum feature size. We have ignored capacitance on wires, since the thickness
interaction between gate voltage and reliability. As you shrink gate voltages, the reliability of the gate in the face of thermal noise declines. 5.7.1 Thermal noise The thermal ﬂuctuations of voltage on a capacitor in a CMOS chip give rise to a thermal noise voltage (Kish, 2004), which has the form Un = kT C (5.26) As the capacitance of the gate falls, the thermal noise rises. Note the similarity of this to the distribution discussed on page 85. The discrete nature of charge lies at the base
1993). These containers were marked with the temple seal to verify who had inserted the tokens. This provided a tamper-proof way of sending and keeping a count of stock. Next, it was realized that it was possible to mark the outside of the container with impressions showing how many tokens were inside. If there were four sheep tokens inside, then a sheep token would be pressed into the outside of the container four times whilst the clay was still soft. It was but a small step, then, to dispense
arranged in two quantum registers: an input register of, say, n qubits and an output register of m qubits. The input register can ‘contain’ any n-bit binary word or any superposition thereof in the sense that it can be described by a state vector that is an element of C2n . Likewise, the output register can contain any m-qubit value that can be described by an element of C2m . Now suppose that we wish to compute some chosen function f (x ) of x, where x and f (x) are n-bit and m-bit binary