Algorithmic Information Theory for Physicists and Natural Scientists

Description

Algorithmic information theory (AIT), or Kolmogorov complexity as it is known to mathematicians, can provide a useful tool for scientists to look at natural systems, however, some critical conceptual issues need to be understood and the advances already made collated and put in a form accessible to scientists. This book has been written in the hope that readers will be able to absorb the key ideas behind AIT so that they are in a better position to access the mathematical developments and to apply the ideas to their own areas of interest. The theoretical underpinning of AIT is outlined in the earlier chapters, while later chapters focus on the applications, drawing attention to the thermodynamic commonality between ordered physical systems such as the alignment of magnetic spins, the maintenance of a laser distant from equilibrium, and ordered living systems such as bacterial systems, an ecology, and an economy. Key Features Presents a mathematically complex subject in language accessible to scientists Provides rich insights into modelling far-from-equilibrium systems Emphasises applications across range of fields, including physics, biology and econophysics Empowers scientists to apply these mathematical tools to their own research PRELIMS.pdf Preface Reference Author biography Sean D Devine Symbols CH001.pdf Chapter 1 Introduction 1.1 Brief outline of the book 1.2 What are complex systems? 1.3 Some approaches to complex or organised systems 1.4 Algorithmic information theory (AIT) 1.4.1 Algorithmic information theory and entropy 1.4.2 Problems with AIT 1.5 Algorithmic information theory and mathematics 1.6 Real-world systems 1.6.1 AIT concepts need to explore the natural world References CH002.pdf Chapter 2 Computation and algorithmic information theory 2.1 The computational requirements for workable algorithms 2.2 The Turing machine 2.2.1 Alternative Turing machines 2.2.2 The universal Turing machine 2.2.3 Non-computable functions 2.3 Measure theory 2.3.1 Cylinder sets References CH003.pdf Chapter 3 AIT and algorithmic complexity 3.1 Shorter algorithms imply order 3.2 Machine dependence and the invariance theorem 3.2.1 Issues with AIT 3.3 Self-delimiting coding and the Kraft inequality 3.4 Optimum coding and Shannon’s noiseless coding theorem 3.4.1 Delimiting coding of a natural number 3.4.2 The relationship with entropy, conditional entropy, etc 3.5 Entropy relative to the common framework 3.6 Entropy and probability 3.7 The fountain of all knowledge: Chaitin’s Omega 3.8 Gödel’s theorem and formal axiomatic systems 3.9 The algorithmic entropy, the universal semi-measure and inference 3.9.1 Inference and and the universal distribution References CH004.pdf Chapter 4 The algorithmic entropy of strings with structure and variation 4.1 Identical algorithmic approaches to strings with variation 4.2 The provisional entropy 4.3 The specification by a probability distribution 4.3.1 The algorithmic minimal sufficient statistics approach to the provisional entropy 4.3.2 Summing up 4.3.3 A simple example of the provisional entropy 4.3.4 Hidden structure and the term ‘provisional’ 4.3.5 Algorithmic entropy not critically dependent on detail 4.4 How to specify noisy data 4.5 The non-typical state and the thermodynamic entropy References CH005.pdf Chapter 5 Modelling and the minimum description length 5.1 Introduction 5.2 The algorithmic entropy approach to modelling 5.2.1 A more general example 5.2.2 The AMSS application to model selection 5.3 The minimum description length approach 5.3.1 Ideal MDL 5.3.2 Example of a non-typical string in a set 5.3.3 Practical MDL 5.3.4 Maximum entropy formulation References CH006.pdf Chapter 6 The non-typical string and randomness 6.1 Outline on perspectives on randomness 6.2 Martin-Löf test of randomness Martin-Löf test examples 6.2.1 Randomness deficiency as a Martin-Löf test 6.2.2 The Martin-Löf universal P-test of randomness 6.2.3 The sum P-test 6.2.4 The use of universal concepts References CH007.pdf Chapter 7 Order and entropy 7.1 The meaning of order 7.2 Algorithmic entropy and the traditional entropy 7.2.1 Specification of the state space 7.2.2 Boltzmann, Gibbs, Shannon and algorithmic entropy 7.2.3 Zurek’s physical entropy, missing information and the algorithmic description 7.2.4 The consistency of the provisional entropy References CH008.pdf Chapter 8 Reversibility, and Landauer’s principle 8.1 Introduction 8.2 Landauer’s principle 8.3 Outline of Landauer’s argument 8.4 The simulation of a reversible real-world computation 8.4.1 Maintaining reversibility in a laboratory UTM 8.5 The algorithmic entropy as a function of state 8.5.1 When bits are tracked, bits are conserved 8.5.2 Must the algorithm that specifies the provisional entropy halt? 8.5.3 Tracking bit flows in non-halting computations 8.6 External interventions to restore a degraded system References CH009.pdf Chapter 9 The algorithmic equivalent of the second law of thermodynamics 9.1 The meaning of ‘equilibrium’ 9.1.1 The source of bits in different scenarios 9.2 The increase in thermodynamic entropy as a system trends to the most probable set of states 9.3 The relationship between algorithmic entropy and the thermodynamic entropy of a macrostate 9.3.1 Simple models illustrating isolated systems 9.3.2 General approach to specifying all states in an isolated system References CH010.pdf Chapter 10 How replication processes maintain a system far from the most probable set of states 10.1 Maintaining a system distant from the equilibrium 10.1.1 Brief summary of the earlier exposition of AIT 10.2 Examples of the computational issues around the degradation of simple systems 10.3 Entropy balances in a reversible system 10.4 Homeostasis and second law evolution 10.4.1 Information requirements of homeostasis 10.5 Replication processes generate order to counter the second law of thermodynamics 10.5.1 Replication as a process that creates ordered structures 10.6 Simple illustrative examples of replication 10.6.1 Replicating spins 10.6.2 Coherent photons as replicators 10.7 The algorithmic entropy cost of replica variations 10.7.1 Natural ordering through replication processes 10.8 A replicating living system 10.9 Selection processes to sustain a natural system 10.9.1 Adaptation and interdependence of replicas in an open system 10.10 Summary of system regulation and AIT References CH011.pdf Chapter 11 Sustainability requirements of a viable economy distant from equilibrium 11.1 Introduction 11.2 A reminder of the principles of AIT 11.2.1 Natural laws as computations 11.2.2 An illustration based on an image on a screen 11.2.3 Replication processes create natural order 11.3 An economy seen as a replicating system 11.3.1 The contrast with a neoclassical economy 11.4 Order creation through the know-how of economic agents 11.5 A narrative to capture economic development 11.5.1 The hypothetical steps to greater economic sophistication 11.5.2 Independent agents 11.5.3 Agent adaptation 11.5.4 Trade increases order 11.5.5 Trade in artefacts 11.5.6 Order created by innovation, tools and machines 11.5.7 Amalgamation and nesting of agents to form new agent types 11.6 Are there resource limits to economic growth? 11.7 Order and GDP 11.8 Complementary approaches to human systems 11.8.1 Control information 11.8.2 Energy flows in low entropy systems 11.9 Implications of the algorithmic approach 11.10 Conclusions for economic systems References CH012.pdf Chapter 12 AIT and philosophical issues 12.1 Algorithmic descriptions, learning and artificial intelligence 12.2 The mathematical implications of algorithmic information theory 12.3 How can we understand the Universe? Why can we make any sense of the Universe? 12.4 Closing thoughts References