Название: Algorithmic Information Theory for Physicists and Natural Scientists
Автор: Sean D Devine
Издательство: IOP Publishing
Год: 2020
Страниц: 238
Язык: английский
Формат: pdf (true), epub
Размер: 10.3 MB

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. AIT is a branch of theoretical Computer Science that concerns itself with the relationship between computation and information of computably generated objects (as opposed to stochastically generated), such as strings or any other data structure. 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.

The Chapter 1 introduces algorithmic information theory (AIT) as a tool to complement the insights of traditional thermodynamics. Key is the insight that natural laws can be understood as computations on a real-world universal computer or universal Turing machine (UTM). The algorithmic entropy, or the information content, of a configuration in the natural world is given by the number of bits in the shortest binary programme that generates the configuration using an instruction set that needs no end-markers. The number of bits aligns with the thermodynamic entropy. Where computational end-markers are needed for the instructions, the terms algorithmic complexity or Kolmogorov complexity are used instead of algorithmic entropy. As only entropy differences matter in nature, and as one UTM can simulate another to within a constant, the number of bits required to change one state to another in the natural world is the same as the number that exactly simulates the process in a laboratory UTM.

The history of AIT or Kolmogorov complexity is outlined with the contributions of key researchers while the ambiguity over terms such as information and complexity is clarified. As real-world computations are reversible, a simulation of a real-world process must also be structured to maintain reversibility. Once bits are tracked in a reversible computation, bits are conserved. Bits specifying the momentum degrees of freedom, allowing for units, align with the thermodynamic entropy, whereas bits carried in stored energy states or in computational instructions correspond to potential thermodynamic entropy. Only when these bits, under the second law of thermodynamics, are transferred to thermal degrees of freedom will the thermodynamic entropy increase.

AIT defines the complexity of a structure or an object by the length of the shortest algorithm that generates the binary string defining the structure. This length is known as the Kolmogorov complexity, the algorithmic complexity or the programme sized complexity of the string. However, there are two variations of the complexity measure. The first is where end-markers are required for the coded instructions or subroutines, to ensure the computer implementing the instructions knows when one instruction is completed before implementing the next. In this case, the hypothetical computational device known as Turing machine (TM) that implements an instruction from an input tape will need to distinguish successive instructions by separating them with blanks, or some other marker. As is discussed further later, the computational instructions where end-markers are used gives rise to what is known as the plain algorithmic complexity.

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