Motivation:
This question is inspired by a talk from Avi Wigderson given on Randomness, where the idea that the randomness is in the eye of the observer is suggested.
In the study of information theory and its applications, an intriguing paradox emerges when considering Kolmogorov complexity and the perception of randomness by observers.
Consider the digits of the mathematical constant $\pi$. The entire infinite sequence of $\pi$'s digits can be generated by a simple algorithm, implying that the Kolmogorov complexity $K(\pi)$ of the entire sequence is low. However, if an observer is presented with a finite substring of $\pi$'s digits without knowledge of its position within the sequence, this substring appears random and exhibits high Kolmogorov complexity. Formally, for a substring $s$ of length $m$ starting at an unknown position $n$, we have: $$ K(s) \approx m $$ since, without additional information, the shortest program to produce $s$ is essentially to output it directly.
Similarly, the Liouville function $\lambda(n)$, defined as $$ \lambda(n) = (-1)^{\Omega(n)}, $$ where $\Omega(n)$ denotes the total number of prime factors of $n$ (counted with multiplicity), maps integers to $\{-1, +1\}$. For large $n$, determining $\lambda(n)$ requires factoring $n$, which is computationally intensive. To an observer without efficient factoring algorithms, the sequence of $\lambda(n)$ values appears random despite being deterministically defined: $$ K(\lambda(n)) \approx m \quad \text{for large } m. $$
These scenarios illustrate how an observer's knowledge and computational capacity influence the perceived Kolmogorov complexity and randomness of a system.
Question:
Given the definitions provided by Bennett, Hoffman, and Prakash, where an observer is modeled as a six-tuple of measurable spaces and functions, what are the possible alternative mathematical definitions of observers that can rigorously account for the observer-dependent perception of Kolmogorov complexity and randomness? Specifically:
- How can we formally define observers in a way that captures the differences in complexity perception illustrated by the $\pi$-Kolmogorov complexity paradox and the behavior of the Liouville function?
- Are there existing frameworks or theories in mathematical logic or theoretical computer science that provide alternative models of observers which could resolve or reinterpret these paradoxes?
- How might these alternative definitions integrate with or diverge from the measurable spaces and Markov kernels approach used by Bennett and colleagues?
Any rigorous mathematical definitions, frameworks, or references to literature that explore different notions of observers in the context of information theory and complexity would be highly valuable.
Appendix: Definition of Bennett, Hoffman, Prakash on observer: An observer is a six-tuple
$$( (X, \mathcal{X}), (Y, \mathcal{Y}), E, S, \pi, \eta )$$
satisfying:
- $(X, \mathcal{X})$ and $(Y, \mathcal{Y})$ are measurable spaces. $E \in \mathcal{X}$ and $S \in \mathcal{Y}$.
- $\pi: X \to Y$ is a measurable surjective function with $\pi(E) = S$.
- Let $\mathcal{E} = \{ E \cap A \mid A \in \mathcal{X} \}$ and $\mathcal{S} = \{ S \cap B \mid B \in \mathcal{Y} \}$ be the $\sigma$-algebras induced on $E$ and $S$, respectively. Then $\eta$ is a Markov kernel from $(S, \mathcal{S})$ to $(E, \mathcal{E})$ such that, for each $s \in S$, $\eta(s, \cdot)$ is a probability measure supported on $\pi^{-1}(s) \cap E$.
The components are named as follows:
- $X$ — Configuration space
- $Y$ — Premise space
- $E$ — Distinguished configurations
- $S$ — Distinguished premises
- $\pi$ — Perspective
- $\eta$ — Conclusion kernel (interpretation kernel)
References:
- Bennett, B. M., Hoffman, D. D., & Prakash, C. (1989). Observer Mechanics: A Formal Theory of Perception. University of California, Irvine.
- Kolmogorov Complexity
- Liouville Function
Disclaimer: Since english is not my native language, I used a chat-assistant to formulate parts of the question.
