Obsidian Source: Notes / The First Law of Complexodynamics.
Summary
Pending synthesis from local Obsidian source.
Original source title: The First Law Of Complexodynamics.
Extracted Preview
The task is to answer a simple question. Why does complexity of physical system plateau(and decrease) but entropy increases monotonically ?
- Scott answered this using Kolmogorov Complexity. KC of a string X is the length of the smallest computer program that outputs X(in some Turing universal computer language.)
- He broke down the problem into 2 tasks, first is using KC to define entropy, and then use KC to define complexity.
- For Task 1, we needed some type of KC that increases polynomially or linearly with time. An example to consider for this is a cellular automaton that evolve over some time. For a non-deterministic case KC increases at polynomial rate but in deterministic case, only $log(t)$ bits are required. A way to induce entropy in this is to use a resource bound KC.
- For Task 2, we use Sophistication as a measure of Complexotropy. Sophistication is the length of the shortest computer program that describes a set $S$ of which $X$ is a random/ generic member. Small KC is small sophistication, and Large KC is also small sophistication. This is the formal mathematical definition of Sophistication.
Given a set $S$ on $n$-bit strings let $K(s)$ be the number of bits in the shortest computer program that outputs the elements of $S$ and then halts. $K(x|S)$ be the length of the smallest program that outputs $x$ , then $Soph(x)$ be the smallest value of $K(s)$ over all sets $S$ such that :
(i) $x \in S$
(ii) $K(x|s) \geq log_2(|S|) - c$ for some constant C
Add resource constraint $n log(n)$ and you have a complexotropy definition. The difficult task is to prove it. It'll be awesome.
Integration Notes
- Source folder:
/home/yashs/Documents/Docs/Obsidian/Research-Notes - Local source:
/home/yashs/Documents/Docs/Obsidian/Research-Notes/Notes/The First Law of Complexodynamics..md - Raw copy:
raw/obsidian/research-notes/Notes/The First Law of Complexodynamics..md