Computation
A physical system “computes” if we can form a fixed “representation relation” mapping its states (up to some level of reliability) to those of a “Turing Machine,” such that the physical evolution of the system over time parallels the abstract evolution of the Turing Machine. Alan Turing defined computation in prosaic terms: it was any sequence of steps that could be carried out by a human computer following unambiguous rules to read, write, and erase symbols, given an unlimited ream of paper and a pencil with an eraser. This abstract construct—the idealized, tireless human worker with paper and a pencil—is a Turing Machine and the symbols written on the tape comprise “algorithmic information,” or “differences that make a difference.” Universal computation is achieved when the rules allow any other set of rules to themselves be written down as symbols and interpreted by the machine, such that the computation performed is given by those written-out rules, which we call a “program” or “algorithm.” If a physical system can be mapped to a Universal Turing Machine, then the computation is universal or “Turing-complete,” no matter what the physical system is made of or how it works; this property is known as “platform independence” or “multiple realizability.” There has also been recent theoretical work to extend Turing’s original, fully deterministic form of computation to the more realistic regime of “stochastic computation,” which exhibits some degree of randomness.