ConceptAI & ML
Kolmogorov complexity
The complexity of something is defined as the length of the shortest explanation or description of that something.
Know first
Named as a prerequisite by the lectures that define this. The number is how many say so. A grey one has no page yet.
Computability theory2Computer program2Turing machine2Algorithm complexity1Bit string1Complexity theory1Description length1Entropy1
Opens up
Concepts that name this one as a prerequisite.
Lecturers
6Each in their own terms, from the easiest level.
Ilya Sutskever
The length of the shortest program that outputs a given piece of data.Karl Friston
Kolmogorov complexity and related literature on minimum description length and algorithmic complexity focus on minimizing the complexity cost of explanations or models.Bruno Bauwens
The definition of amount of information in an individual bit string, defined as the compression limit.John Carlos Baez
A notion of entropy that lets you define a concept of entropy for a single finite-length bit string.John M. Aiken
The length of the shortest computer program in a predetermined programming language that produces a given object as output.
Lectures that assume it
1Connections
15The lectures that define it or assume it, and the concepts next to it.
Concepts8
- Computability theory
- Computer program
- Turing machine
- Algorithmic thermodynamics
- Conditional Kolmogorov complexity
- Information distance
Show 2 moreShow fewer
Lectures7
- Inner Simplicity vs. Outer Simplicity
- An Observation on Generalization and Unsupervised Compression
- The Physics of Motivation: An Active Inference Perspective
- Algorithmic Thermodynamics
- HSE Kolmogorov Complexity, Lecture 1: Computability and Solomonoff Induction
- Exploring System Dynamics in the Natural World with AI