A Simplicity Criterion for Physical Computation. (30th August 2017) - Millhouse, Tyler
Abstract: The aim of this article is to offer a formal criterion for physical computation that allows us to objectively distinguish between competing computational interpretations of a physical system. The criterion construes a 'computational interpretation' as an ordered pair of functions mapping (i) states of a physical system to states of an abstract machine, and (ii) inputs to this machine to interventions in this physical system. This interpretation must ensure that counterfactuals true of the abstract machine have appropriate counterparts which are true of the physical system. The criterion proposes that rival interpretations be assessed on the basis of simplicity. Simplicity is construed as the Kolmogorov complexity of the interpretation. This approach is closely related to the notion of algorithmic information distance and draws on earlier work on real patterns. 1 Introduction 1.1 Philosophical background 1.2 Information distance 2 Computers and Computation 2.1 Computational interpretations 2.2 A new criterion for implementation 2.3 Kolmogorov complexity 2.4 The simplicity criterion 3 Some Lingering Concerns 3.1 Demarcation and the hard work of computation 3.2 Imperfect implementation 3.3 Practical difficulties 4 Conclusion