PaperlayerView exact revision on arXiv

Source-linked AI summary

When does a physical system compute?

Dominic Horsman, Susan Stepney, Rob C. Wagner, Viv Kendon

arXiv:1309.7979v3cs.ETphysics.hist-phquant-ph

TL;DR

The paper asks how to distinguish genuine physical computation from ordinary physical evolution and confusion surrounding unconventional systems. It develops a representation-based framework linking abstract computations to physical dynamics, concluding that computation requires a sufficiently commuting abstract–physical relation and a computational entity.

  • Problem

    There is no accepted formal answer for determining when a physical system is acting as a computer, creating confusion about unconventional computation and trivializing claims that everything computes.

  • Method

    The paper models physical computation through theory-dependent representation relations connecting physical systems, abstract computations, and their respective evolutions.

  • Results

    Physical computing is characterized by using a physical system to predict an abstract evolution when the abstract–physical diagram commutes sufficiently for its intended purpose.

  • Takeaways & Limitations

    The framework distinguishes computation from experiment and engineering, and applies without requiring an intention-bearing or conscious human user.

Abstract

from arXiv · show

Computing is a high-level process of a physical system. Recent interest in non-standard computing systems, including quantum and biological computers, has brought this physical basis of computing to the forefront. There has been, however, no consensus on how to tell if a given physical system is acting as a computer or not; leading to confusion over novel computational devices, and even claims that every physical event is a computation. In this paper we introduce a formal framework that can be used to determine whether or not a physical system is performing a computation. We demonstrate how the abstract computational level interacts with the physical device level, drawing the comparison with the use of mathematical models to represent physical objects in experimental science. This powerful formulation allows a precise description of the similarities between experiments, computation, simulation, and technology, leading to our central conclusion: physical computing is the use of a physical system to predict the outcome of an abstract evolution. We give conditions that must be satisfied in order for computation to be occurring, and illustrate these with a range of non-standard computing scenarios. The framework also covers broader computing contexts, where there is no obvious human computer user. We define the critical notion of a 'computational entity', and show the role this plays in defining when computing is taking place in physical systems.

I. INTRODUCTION

The paper addresses the unresolved physical question of what counts as a computer, especially for unconventional systems, and introduces a framework to determine when physical computation occurs.

  • I. INTRODUCTION: No accepted answer currently determines whether a physical system is computing.This absence creates confusion about unconventional systems and physical computation.
  • I. INTRODUCTION: Unconventional proposals raise difficult boundary cases, including whether proteins, photons, minds, dogs, or stones compute.These examples motivate the need for a nontrivial criterion beyond labeling every physical process computation.
  • I. INTRODUCTION: Defining every physical process as computation makes the claim either false or trivial and therefore practically uninformative.The paper rejects this position as unable to determine properties of physical systems in practice.
  • I. INTRODUCTION: The authors introduce a framework connecting physical systems and mathematically defined computations through representation relations.The framework specifies how the physical and mathematical levels interact and gives necessary conditions for physical computation.
  • I. INTRODUCTION: The framework includes a computational entity as necessary for computation without requiring intention or a conscious human user.This extends the account to contexts lacking an obvious human computer user.

II. PHYSICAL COMPUTATION

Physical computation concerns the relationship between abstract computations and physical systems, mediated by a representation relation rather than causation between the two domains.

  • II. PHYSICAL COMPUTATION: A computation is an abstract mathematical or logical entity, whereas a computer is a physical system that changes state through internal interactions.The paper frames computing as a relation between these distinct levels.
  • II. PHYSICAL COMPUTATION: The central problem is explaining how an abstract computation can interact with a physical system without treating the relation as causation.The paper identifies this as a category error and seeks another bridge between the domains.
  • II. PHYSICAL COMPUTATION: Physics supplies the model for this interaction by representing physical systems abstractly, using theory to predict physical evolution, and testing predictions experimentally.This provides the conceptual basis for the paper’s framework for physical computation.
  • II. PHYSICAL COMPUTATION: The representation relation maps between spaces of physical and abstract objects, illustrated by an electron and a wavefunction.Figure 1 presents this relation as the bridge across the abstract–physical divide.

III. PHYSICS AND THE REPRESENTATION RELATION

The paper adopts physics’ representation relation as the basis for connecting physical devices to abstract computations, emphasizing its theory dependence and asymmetric directions.

  • III. PHYSICS AND THE REPRESENTATION RELATION: In physics, the representation relation gives physical systems abstract descriptions such as wavefunctions, phase-space points, or metric tensors.Representations may be mathematical, logical, or linguistic, with their precision affecting what can be studied.
  • III. PHYSICS AND THE REPRESENTATION RELATION: The representation relation uniquely maps between physical and abstract spaces rather than functioning as an ordinary mathematical relation.Its precise nature remains a subject of philosophical investigation.
  • III. PHYSICS AND THE REPRESENTATION RELATION: The representation of a physical system is not unique and depends on the theory used to describe it.For example, an electron can receive different representations in quantum mechanics, classical mechanics, and quantum field theory.
  • III. PHYSICS AND THE REPRESENTATION RELATION: Modelling maps an existing physical entity p to an abstract model m_p, while instantiation seeks a physical system corresponding to an abstract entity.These directions are asymmetric because abstract models can be created without generally providing matching physical systems.
  • III. PHYSICS AND THE REPRESENTATION RELATION: Figure 2 shows theory and experiment evolving in parallel: a physical system is modelled, evolved abstractly and physically, then compared through re-representation.This framework forms the basis for defining physical computation.

IV. THEORY AND EXPERIMENT IN PHYSICS

Experiments test whether abstract theory and physical evolution agree under a shared representation, accepting contextual closeness rather than requiring exact identity.

  • IV. THEORY AND EXPERIMENT IN PHYSICS: Experiments test whether a physical theory provides a sufficiently accurate model of physical evolution.The experimental setup evolves physically while the theory predicts an abstract final state for comparison.
  • IV. THEORY AND EXPERIMENT IN PHYSICS: Physical theories are theory-dependent representations whose models undergo abstract dynamics, while the corresponding physical systems undergo their own dynamics.The two resulting states must be compared through the representation relation.
  • IV. THEORY AND EXPERIMENT IN PHYSICS: The physical outcome p′ is re-represented as m_p′ so it can be directly compared with the abstract prediction m′_p.A modelling relation alone cannot construct a physical system from the predicted abstract state.
  • IV. THEORY AND EXPERIMENT IN PHYSICS: Practical agreement requires the prediction and represented outcome to be close enough, |m′_p − m_p′| < ϵ, with ϵ determined by experimental context.Experimental error and modelling limitations make exact commutation more stringent than ordinary practice.
  • IV. THEORY AND EXPERIMENT IN PHYSICS: The diagrams represent physical objects below the line by abstract objects above it, unlike superficially similar abstract-interpretation diagrams.The distinction concerns physical-to-abstract representation rather than concrete operational semantics.

V. COMMUTING DIAGRAMS

The paper models experiments as commuting diagrams linking physical evolution, abstract evolution, and representation. Testing a theory evaluates the combined dynamics and apparatus representation under specific experimental conditions.

  • Experimental diagrams: A theory and apparatus jointly generate abstract predictions for a physical experiment’s evolution.The physical setup evolves from p to p′, while the combined theory produces an abstract prediction m′.
  • Experimental diagrams: The experiment’s final physical state is modelled again so its outcome can be compared with the abstract prediction.This second modelling step translates detector states into an abstract description of the observed result.
  • Theory testing: A successful experiment yields a commuting diagram only for the tested dynamics and representation, not for the isolated target theory.The tested theory includes both Ttest and Tapparatus, so apparatus assumptions must also be validated.
  • Theory testing: Experimental science relies on apparatus theories that have themselves been tested through their own commuting diagrams.Errors in the apparatus dynamics or modelling can flaw the experiment.
  • Theory testing: The framework describes scientific validation as satisfying many interlocking commuting diagrams across known cases.The resulting theories are trusted to produce commuting diagrams for other specified physical systems and dynamics.

VI. REVERSING THE MODELLING RELATION: PREDICTION AND TECHNOLOGY

The paper treats prediction and technology as reversals of the physical-to-abstract modelling relation. Abstract evolution can predict physical outcomes, while engineering uses trusted theories to construct physical systems matching desired abstract specifications.

  • Prediction: The predict cycle uses abstract evolution instead of physically evolving a system to obtain the predicted abstract outcome.This requires confidence that the complete physical–abstract diagram commutes.
  • Prediction: Instantiation asks which physical system would model to an abstract object produced by prediction.Finding that system requires a set of commuting diagrams and substantial theoretical and experimental skill.
  • Prediction: Dirac’s prediction of positrons exemplifies using a tested theory to connect a novel abstract object with a previously unknown physical system.The prediction relied on experimentally tested theory and knowledge of its modelling behaviour beyond tested cases.
  • Technology: Technology reverses modelling by constructing physical systems that realize desired abstract specifications.Engineers seek p, T, and H such that physical evolution produces a final state represented as the desired m′p.
  • Technology: Reversing modelling is not mechanical: selecting suitable physical systems, theories, and evolutions requires ingenuity and skill.The reversed relation depends on a sufficiently advanced theory whose diagrams commute in the intended cases.

VII. WHEN DOES A PHYSICAL SYSTEM COMPUTE?

A physical system computes when a trusted theory and bidirectional representation connect its physical evolution to an abstract computation. The compute cycle encodes abstract input, applies physical dynamics, and decodes the resulting physical state as the abstract outcome.

  • Requirements: A computer requires a tested theory that supports commuting diagrams for the relevant device states and evolutions.The theory must cover the representation relation and physical dynamics beyond only the exact cases used in testing.
  • Input and encoding: Computation begins with an abstract problem that is embedded into a machine description and encoded in a physical system.Embedding may transform an informal problem into a form suitable for manipulation by the computer.
  • Execution and output: In the binary-addition example, encoded voltages undergo physical dynamics and are decoded into the abstract result.The physical evolution implements the operation, while final modelling yields the abstract state m′p.
  • Definition and framework: Physical computing uses a physical system to predict the outcome of an abstract evolution via a commuting compute cycle.Unlike experiment, the physical route connects an abstract input to an abstract output through the computer.
  • Requirements: All required elements must be present before a physical system can be identified as acting as a computer.The conditions include a tested theory, bidirectional representation, at least one computational operation, and relevant commuting diagrams.
  • Requirements: The representation must work in both directions: encoding initializes the physical system from abstract data, and decoding produces an abstract output.The paper explicitly requires a representation {RT, eRT} for both initial and final states.

VIII. PHYSICAL DYNAMICS AND COMPUTER PROGRAMS

Computer programs describe abstract computations that are refined into fundamental physical operations. The embedding from problem to machine therefore consists of successive abstract transformations before encoding into the device.

  • Physical dynamics: Physical computer dynamics are generally composed of smaller units such as logic gates or other dynamical operations.Examples include quantum-annealing relaxation and operations in differential analysers.
  • Programs and compilation: An algorithm must be refined into fundamental operations before it can be implemented on a physical computer.In gate-based systems, the resulting operations are composed into a sequence for execution.
  • Programs and compilation: Embedding a problem into a computer can be viewed as successive embeddings into an algorithm, machine description, and physical encoding.This expands the abstract problem-embedding process into the stages needed for device execution.

A. Refinement

Refinement moves an abstract algorithm through increasingly concrete, mathematically specified implementations before physical realization. Its feasibility depends on available embeddings and, for unconventional devices, on controlling approximation and error propagation.

  • A. Refinement: Refinement transforms an abstract algorithm into a suitably equivalent concrete algorithm implementable on a computer.
  • A. Refinement: Decimal addition can be refined through binary addition to an assembly-language implementation, with each level remaining in the mathematical realm.
  • A. Refinement: Unconventional devices may realize refinement only approximately, requiring error propagation to be considered when computations are sequenced.
  • A. Refinement: The boundary between mathematical refinement and physical implementation is a design choice determined by the sophistication of the physical device.
  • A. Refinement: Refinement is possible only when the required embedding exists; finite hardware may be unable to represent arbitrarily large abstract computations.

B. Composition

Physical computation combines abstract operations through both individual gate theories and a compositional theory. The resulting physical computer is governed by a theory tested to predict outcomes in previously unknown situations.

  • B. Composition: A physical implementation of a gate requires a physical system, representation relation, and dynamics whose diagram commutes with the abstract evolution.
  • B. Composition: Each gate is tested separately, while a compositional theory specifies how gates combine without contradicting one another.
  • B. Composition: The computer’s theory combines the compositional theory with individual gate theories and is extended and tested like a physical theory.
  • B. Composition: Confidence in the resulting theory supports predictions of computational outcomes in situations that are unknown, within the theory’s limits.

IX. COMPUTATIONAL ENTITIES

Physical computing requires representation between abstract data and a physical system, including encoding and decoding performed by a computational entity. This requirement distinguishes computation from ordinary physical evolution without making the criterion inherently subjective.

  • IX. COMPUTATIONAL ENTITIES: Encoding abstract data or programs into a physical system and decoding its final state into an abstract output are necessary steps of physical computation.
  • IX. COMPUTATIONAL ENTITIES: A computational entity is required because it establishes the representation relation between the abstract computation and the physical device.
  • IX. COMPUTATIONAL ENTITIES: The existence of a computational entity is treated as an objective requirement because encoding and decoding cannot otherwise be defined.
  • IX. COMPUTATIONAL ENTITIES: Computational entities need not be human; anything capable of encoding and decoding information can fulfill that role.
  • IX. COMPUTATIONAL ENTITIES: A physical computer can continue the same evolution without computing when the computational entity is removed before decoding.
  • IX. COMPUTATIONAL ENTITIES: Computational entities may include artificial systems, and human involvement alone does not establish that the human is performing the encoding or decoding.

X. COMPUTATION AND SIMULATION

The framework treats simulation as prediction implemented through computation: a physical simulator uses representations and embeddings to predict another system’s abstract evolution. Simulation requires encoding, decoding, and representational stages, including when a system simulates itself.

  • Validation: A valid simulator requires the relevant abstract and physical diagrams to commute, supported by a sufficiently reliable theory of the devices.This confidence allows the system to move from testing the simulator to using it predictively.
  • Representation and embedding: The setup represents p abstractly, embeds that representation into s, instantiates it physically, then decodes and de-embeds the simulator’s output.The embedding may encode scale factors or other mappings between the abstract descriptions of p and s.
  • Simulation as prediction: Simulation uses a physical system s to predict the evolution of another physical system p without physically evolving p.The simulator’s dynamics replace the simulated system’s physical evolution while targeting a matching abstract outcome.
  • Nested cycles: The computation in simulation is a compute cycle nested within a predict cycle, with the simulated dynamics embedded into the simulator’s abstract dynamics.The physical simulator ultimately determines an abstract evolution through its own compute cycle.
  • Non-standard and self-simulation: Non-standard systems such as wind tunnels, models, and pendulums can serve as simulators when their representations, embeddings, and decoding operations are specified.The framework does not restrict simulation to standard digital computers.
  • Non-standard and self-simulation: Self-simulation does not follow merely from identical systems or identity embeddings; initial and final representational stages remain necessary.Without those representational stages, the physical system is not simulating itself.

XI. NON-STANDARD COMPUTING: COMPUTATION OR EXPERIMENT?

The framework distinguishes physical computing from experimentation and post-hoc description by requiring predictive confidence in the abstract/physical correspondence. Non-standard substrates expose limits involving physical theory, scaling, and extrapolation.

  • Computing versus experiment and engineering: Prediction is essential to computing because the physical system must be used to predict an abstract evolution beyond the tested domain.Without this predictive element, a physical system is not a computer.
  • Post-hoc computational claims: Choosing a computational description after observing only initial and final states permits almost any computation to fit and does not establish computing.The framework rejects descriptions that can only be applied post-hoc.
  • Theory and scaling limits: Non-standard devices often rely on phenomenological models that match inputs to outputs without describing all underlying physics.Such models require greater confidence that relevant changes are captured and generally lack scalable device theories.
  • Computing versus experiment and engineering: Physical computing requires confidence that the abstract/physical diagram commutes; otherwise the system is being engineered or experimentally assessed, not computing.A mismatch can prompt redesign in engineering or challenge the theory in science.
  • Theory and scaling limits: Evolved LCD substrates may compute within the experimentally characterized domain but cannot be meaningfully extrapolated outside it with confidence.The absence of a physical model prevents confident scaling of the device.
  • Theory and scaling limits: Slime moulds and LCD devices scale by using larger versions of the same system, but phenomenological performance models do not guarantee desired behaviour after scaling.This contrasts with the compositional scaling of digital computers.
  • Theory and scaling limits: Even a physical model can misrepresent an unconventional device’s behaviour: soap films may become trapped in local states instead of finding minimum states.The paper notes that soap films follow stationary-action behaviour rather than always minimizing action.

XII. CONCLUSION

The framework connects physical and abstract computation through representation, requiring a physical theory, encoding and decoding, and at least one fundamental dynamical operation. It clarifies unconventional computing by distinguishing computation from experimentation and situates physical computing alongside science, technology, and engineering.

  • Formal framework: The framework connects physical and abstract levels through representation, using physical evolution to determine the outcome of an abstract computation.It adapts diagrams that connect abstract theory with physical experiments.
  • Conditions for computation: Computation requires a good physical theory, representation for encoding and decoding information, and at least one fundamental dynamical operation.Encoding and decoding imply the presence of computational entities that locate the representation.
  • Broader implications: The framework also describes the relationships among theoretical and experimental science, computation, engineering, technology, and physical-system simulation.It addresses confusion about what is simulated and how simulations relate to physical systems.
  • Unconventional computing: The framework clarifies unconventional devices by showing that insufficient device theory can mean users are experimenting on them rather than computing with them.Confidence that computation is occurring depends on whether the relevant computational diagrams commute.
  • Broader implications: The framework provides a precise language for describing how physical objects interface with logical, mathematical, and computational structures across science, technology, and computing.It presents physical computing as a domain connected to physics, chemistry, and biology.
Loading 1309.7979v3…