Computation in Physical Systems

For example, when something burns, a natural sign forms which we call smoke, and the meaning we attach to the sign is that there is a fire.

"A closely related problem is that of distinguishing between physical systems such as digital computers, which appear to compute, and physical systems such as rocks, which appear not to compute. Unlike computers, ordinary rocks are not sold in computer stores and are usually not considered computers. Why? What do computers have that rocks lack, such that computers compute and rocks don't? (If indeed they don't?) In other words, what does it take for a computation to be implemented in a concrete physical system? Different answers to these questions give rise to different accounts of concrete computation."

...

"Consider a rock under the sun, early in the morning. During any time interval, the rock's temperature rises. The rock goes from temperature T to temperature T+1, to T+2, to T+3. Now consider a NOT gate that feeds its output back to itself. At first, suppose the NOT gate receives ‘0’ as an input; it then returns a ‘1’. After the ‘1’ is fed back to the NOT gate, the gate returns a ‘0’ again, and so on. The NOT gate goes back and forth between outputting a ‘0’ and outputting a ‘1’. Now map physical states T and T+2 onto ‘0’; then map T+1 and T+3 onto ‘1’."

According to the simple mapping account, the rock implements a NOT gate undergoing the computation represented by ‘0101’.

By contast, according to the counterfactual account, the rock's putative computational implementation is spurious, because the physical state transitions do not support counterfactuals. If the rock were put in state T, it may or may not transition into T+1 depending on whether it is morning or evening and other extraneous factors. Since the rock's physical state transitions that map onto the NOT gate's computational state transitions do not support counterfactuals, the rock does not implement the NOT gate according to the counterfactual account."

"The expressive power of real numbers may be used to generate a simple recipe to obtain the values of a Turing-uncomputable function. Consider that the digital expansion of a real number contains countably many digits. Hence, for any characteristic function (i.e., a function whose values are ‘0’ or ‘1’) defined over a countable domain, including all Turing-uncomputable such functions, there is a real number whose binary expansion encodes its values. This is because for all values of a characteristic function, the nth value of the function may be defined to be the nth digit of the binary expansion of a real number.

Suppose you wish to know the value of a specific Turing-uncomputable characteristic function, such as the halting function for Turing machines, for its nth argument. Take the real number r whose digital expansion encodes the values of the halting function. All you need to do is obtain the value of the nth digit in the binary expansion of r and you have the result you desire. If you can do this, you may obtain any value of any characteristic function defined over strings, including all Turing-uncomputable such functions."

"Perhaps the best known proposal for a hypercomputer is due to Mark Hogarth (1994, 2004), who developed an idea of Itamar Pitowsky (1990). Relativistic hypercomputers exploit the properties of a special kind of spacetime called Malament-Hogarth spacetime, which is physically possible in the sense of constituting a solution to Einstein's field equations for General Relativity. Malament-Hogarth spacetimes contain regions with an infinite time-like trajectory λ that can be circumvented by a finite time-like trajectory γ. In other words, λ and γ have a common origin, and there is a spacetime point p on γ such that λ, even though it is infinite, lies entirely in p's chronological past. If an observer launches a Turing machine along λ and then travels along γ she may, within finite time, find herself in the future of an infinitely long computation performed by the Turing machine. If the Turing machine is able to send signals to the observer, the observer would be able to know the outcome of a potentially infinitely long computation, thereby having computational means more powerful than (ordinary) Turing machines. For instance, an observer may be able to obtain the results of an arbitrary instance of the halting function for Turing machines.

Constructing and using a relativistic hypercomputer is a nontrivial affair."