4.4: Algorithmic Complexity and Compressibility
Download as PPTX, PDF
0 likes32 views
This document discusses the properties of algorithmic complexity and compressibility, including unpredictability which refers to the impossibility of predicting an outcome, incompressibility meaning something random cannot be described simply or shortly, and typicality where a random event has nothing special about it. It also examines program-size characterization and its most relevant properties in algorithmic complexity.
4.4: Algorithmic Complexity and Compressibility
- 2. Properties
- 3. Unpredictability That is, the impossibility to predict an outcome or an object.
- 4. Incompressibility That is, that one cannot describe something random in a simple or short fashion, and
- 5. Typicality That is, that a random event does not have anything particularly special.
- 12. Most relevant properties of algorithmic complexity
- 13. Most relevant properties of algorithmic complexity
- 14. Most relevant properties of algorithmic complexity