Two Complexities
Jean‐Pierre Briffaut, Philippe Kourilsky · 2023
Objects with a simple structure have short minimal programs, and these produce their results without requiring large computational resources. To be authentically organized or structurally complex, an object must be able to be described quite briefly by a program or something similar to it, which takes a fairly long time to run. The non-computability that has sometimes been wrongly seen as an obstacle to the practical use of Kolmogorov complexity and Bennett's logical depth is in fact surmountable because of data compression algorithms. A good measure of structural complexity must have the property of not increasing suddenly during a dynamic process, because the structure content cannot increase suddenly without a lot of calculations having been performed. The idea of complexification, the topic of many commentaries and just as many speculations, is becoming a scientific and mathematical subject based on a rigorous general theory and which, in the simplest cases, produces measurement tools.